Re: The modern mathematical concept of infinity is indefensible

In article
<16457079.1232557274552.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
"G. Rodrigues" <sorlakind@xxxxxxxxxxx> wrote:

In article
<19312788.1232478555757.JavaMail.jakarta@xxxxxxxxxxxxx
forum.org>,
"G. Rodrigues" <sorlakind@xxxxxxxxxxx> wrote:

Do you know the recursion theorem? In rough terms,
it states that if you have a rule f such that you
know f(0) and given f(n) you can compute f(n + 1)
then you can extend f to a function N -> N, N the set
of natural numbers. In order to avoid infinite sets,
view functions as computer scientists do, as black
boxes that given an input spit out an output, so that
the recursion theorem just says that given the
hypothesis we can compute f(n) for every natural
number. "We can compute" means, or can be made to
mean, computing in finite time, although in practice
finite can be impractically large. This is an
idealized situation, of course, but as a
self-proclaimed physicist you surely do not object to
it since, after all, *all* models of physics and
engineering are idealized situations.

Not what I think of as the recursion theorem, even
very roughly.


Right, there is a missing sentence there. Let me rewrite the beginning as:

The recursion theorem is a fundamental pillar of computer science since it provides the formal justification for *recursion definitions*. In rough terms, if you have a rule f

And continue as above. Is this more pallatable?

The correction is moot though, since mr. de Bruijn seems to have chosen not to answer this or any other of mny objections.

Primitive recursive functions are defined. The primitive
recursive functions is the smallest class, C, that contains

1) constant functions: lambda xy...z[m]
2) succesor functions: lambda x[x+1]
3) the identity functions: lambda xy...z[w], w = x, y, ...
4) function compostion of prf's.

5) If g(x) and h(x,y,z) are prf's then f satisfying

f(0,x) = g(x)
f(y+1,x) = h(y, f(y,x),z)

is in C.

Here is what I think of when I hear "the recursion theorem."
Let T_1, T_2, ... be an enumeration of Turing machine.

The recursion theorem: If f is a primitive recursive
function then there is an n such that

T_{f(n)} = T_n.

--
Michael Press
.

Relevant Pages

  • Re: Question about extensions of PA
    ... > Nothing but a trivial application of the recursion theorem is needed. ... What guarantees that the resulting fixed point is consistent? ... arithmetical sentences, i.e. the inconsistent theory, as follows from ...
    (sci.logic)
  • Re: Countably infinite Hausdorff topology?
    ... forced to face with the ugly details of "transfinite recursion". ... On the Application of the Transfinite Recursion Theorem (specialized to ... "set theory" appendix to his General Topology ...
    (sci.math)
  • Re: For All x
    ... system will prove the needed definition by recursion theorem (or even ... inductivity, since you don't have unions or intersections, etc. that ... chain of predecessors ...
    (sci.logic)
  • Re: Absolute Continuity
    ... recursion (just go and ask ... recursion theorem is well known to topos theorists. ... definitions of infinite object are equivalent) but if it gives you any ...
    (sci.math)
  • Re: The modern mathematical concept of infinity is indefensible
    ... mean, computing in finite time, although in practice ... Not what I think of as the recursion theorem, ... since mr. de Bruijn seems to have chosen not to answer this or any other of mny objections. ...
    (sci.math)