Re: arithmetic in ZF
- From: "george" <greeneg@xxxxxxxxxx>
- Date: 14 Apr 2005 10:55:04 -0700
Daryl McCullough wrote:
> I think that what Torkel is saying
No, you don't.
Torkel manifestly obviously IS NOT *saying* that,
EVEN if he believes it, and you don't think that he
is saying it, even if you think he believes it.
My point being that people of good will generally
have a serious problem with what Torkel chooses
to actually SAY here, as OPPOSED to what he might
mean or believe. If he would SAY something reasonable
then this kind of thing wouldn't keep happening.
> is that there are algorithms
> (recipes for calculating)
> that don't involve Turing Machines.
To the extent that they are functional and the
functions that they emulate are in turn TM-emulatable,
saying this is NOT helping TF's side of this argument.
> 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.
> 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.
If you want something different, get something DIFFERENT!
Like a pushdown automaton with 2 stacks or something.
>
> The claim of Church's thesis (or at least,
> one interpretation of it)
> is that any deterministic algorithm
> for computing a function from
> naturals to naturals can be simulated
> on a Turing machine. In other
> words, for any algorithm A for computing a
> function of the naturals
> involving pencil, paper, index cards, pebbles,
> etc.,
The CORRECT phrasing of "algorithm for computing a function
of the naturals involving pencil, paper, index cards,
pebbles, etc." is "algorithm". 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.
That wording also involved the adjectives "computable"
and "natural". If "algorithm" HAD A CLEAR PRIOR natural-
langauge definition, there would be nothing to argue over.
IT DIDN'T. It has a VAGUE prior natural definition and
thesis is a stab at a formal approximation of that. As time
goes by the approximation necessarily gets closer, as people's
natural-language intuitions fail to actually produce anything
that escapes the formal version.
> there is a corresponding Turing machine program A'.
"Corresponding" is a matter of degree.
> But A and A' are not the
> *same* algorithm,
They ARE IF the correspondence is CLOSE enough.
And you can make it close. Dialect is not sufficient
to make algorithms different. It IS meaningful to allege
that the SAME algorithm has been IMPLEMENTED in DIFFERENT
ways.
.
- Follow-Ups:
- Re: arithmetic in ZF
- From: Daryl McCullough
- Re: arithmetic in ZF
- From: Aatu Koskensilta
- Re: arithmetic in ZF
- From: Torkel Franzen
- Re: arithmetic in ZF
- References:
- arithmetic in ZF
- From: H. Enderton
- Re: arithmetic in ZF
- From: george
- Re: arithmetic in ZF
- From: Daryl McCullough
- arithmetic in ZF
- Prev by Date: Re: arithmetic in ZF
- Next by Date: Re: arithmetic in ZF
- Previous by thread: Re: arithmetic in ZF
- Next by thread: Re: arithmetic in ZF
- Index(es):
Relevant Pages
|
