Re: Computable functions/reals.

On 17 Aug, 17:18, Gc <Gcut...@xxxxxxxxxxx> wrote:
On 17 elo, 18:47, ju...@xxxxxxxxxxxxx wrote:
On 17 Aug, 15:57, Gc <Gcut...@xxxxxxxxxxx> wrote:

In every book about recursive functions f:N--->N it
is said that they calculate exactly the same stuff than the ordinary
Turing machines.

I would think: of course they do. I don't get if you repeat this
because you are in doubt, or maybe because nobody has explicitly
aknowledged it, or it is just an opening statement to introduce what
is to come. Anyway, it would seem to me quite "obvious" that that must
indeed be the case. Isn't it "obvious"?

When we are speaking about Turing machines some other posters say we
are not necessarily restricted "essentially" or otherwise to the
functions on naturals.

I am far from authoritative on this, but I would instead say exactly
the opposite: Turing Machines *essentially* are the same as recursive
functions on the naturals. The fact is, if I get it correctly, that
some posters avoid that restriction to reintroduce it indirectly in
the form of some constraints to the input/output.

But I think anybody here approves that what
things are in absolute sense computable are computable by the Turing
machines. I try the make a point that the Turing machines are
essentially recursive functions on N by the literature, but I know
from the exprerience that I can`t be sure if I understand the things
correctly - yet.

I can't be sure either, but it seems to me that your thesis is in fact
trivially true.

-LV
.

Relevant Pages

  • Notions of computation
    ... formalizing the same notion of computation: Turing machines, ... recursive functions, lambda calculus, combinatory logic, etc. ... basic facts as "the union of recursive languages is recursive" and "if ... one on that tape, and then these all tapes on this one tape" instead ...
    (comp.theory)
  • Re: A qn on primitive recursive functions
    ... > discussing recursive functions BEFORE we meet Turing machines, ... > course, remember, before we've heard of Turing machines, etc.] speculate ... > that the total recursive functions are ALL the intuitively computable ... then the diagonalization trick will necessarily generate ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... abstraction or extension, IMHO, by the Church-Turing thesis. ... can extend Turing machines the way Mr. Ullrich or anyone else does. ... machines are intuively computable functions on N and all intuively ... all recursive functions on N are turing machines. ...
    (sci.logic)
  • Re: Notions of computation
    ... formalizing the same notion of computation: Turing machines, ... recursive functions, lambda calculus, combinatory logic, etc. ...
    (comp.theory)
  • Re: consistency of arithmetic
    ... that PA is consistent through semantics. ... of the naturals from a handful of intuitive concepts such as 0, 1, ... nonstandard models with 'supernatural' numbers. ... This does not imply that we are not Turing machines; ...
    (sci.math)