Re: arithmetic in ZF

george says...
>Daryl McCullough wrote:

>> Quite often, an algorithm is described as a
>> sequence of rules for manipulating figures on a piece
>> of paper.
>
>That is TM-equivalent; the paper is the tape and the
>figures are the output.

Yes, TM-equivalent in some sense, but not TM-equal.
It's an algorithm, and it is not a Turing machine program.
So not every algorithm is a Turing machine program.
It *can* be turned into a Turing machine program.
That's what Church's thesis says---that every algorithm
in the more general sense can be converted into an equivalent
Turing machine program.

>> Or an algorithm can be given in terms
>> of abacus moves, or in terms of manipulations
>> of index cards or piles of pebbles.
>
>All of those are so VERY TM-emulatable that it
>is meaningful to speak of a TM as running THE SAME
>algorithm as OPPOSED to the TM-analogue of the algorithm.

Well, I'm not sure what notion of equality you are using
for algorithms.

>The thesis IS A PROPOSED DEFINITION of ALGORITHM, NOT of
>"effectively computable function on naturals into naturals".
>DESPITE the fact that Turing's original wording involved functions.

Well, if it's a definition, it's boring. If it's a claim
about what is effectively computable, then it is interesting,
since it could (conceivably) turn out to be false.

It turns out that the class of functions that are computable
using register machines is exactly the same as the class of
function computable using the lambda calculus, which is exactly
the same as the class of function computable using Turing machines,
which is exactly the same as the class of Godel's partial recursive
functions. These were different concepts of "computable function"
that turned out to be equivalent. That's an interesting result.

--
Daryl McCullough
Ithaca, NY

.