arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: george on 14 Apr 2005 09:17 TF> The thesis that "algorithm" means "algorithm implementable TF> on a Turing machine" is trivially false. It may be trivially circular but that is NOT the same thing as trivially false (actually, OBVIOUSLY, it is NOT trivially circular EITHER). Here are some other people mired in this allegedly trivial alleged falsehood: (Wikipedia) The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm (cs 126(a)princeton in '01) What is an algorithm? Informally: a step-by-step procedure for solving a problem. Formally: a Turing machine.
From: Daryl McCullough on 14 Apr 2005 11:21 In article <1113483455.623893.270440(a)l41g2000cwc.googlegroups.com>, george says... > >TF> Church's thesis states that every function computable >TF> by an algorithm is computable by a Turing machine. >TF> The thesis that "algorithm" means "algorithm implementable >TF> on a Turing machine" is trivially false. > >That statement is trvially contradictory, unless there are >algorithms out there that are good for doing things >more important than merely computing functions. >What sorts of things can those algorithms do? I think that what Torkel is saying is that there are algorithms (recipes for calculating) that don't involve Turing Machines. Quite often, an algorithm is described as a sequence of rules for manipulating figures on a piece of paper. Or an algorithm can be given in terms of abacus moves, or in terms of manipulations of index cards or piles of pebbles. 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., there is a corresponding Turing machine program A'. But A and A' are not the *same* algorithm, they just compute the same function. -- Daryl McCullough Ithaca, NY
From: george on 14 Apr 2005 13:55 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.
From: Torkel Franzen on 14 Apr 2005 14:06 "george" <greeneg(a)cs.unc.edu> writes: > The thesis IS A PROPOSED > DEFINITION of ALGORITHM, No it's not.
From: Aatu Koskensilta on 14 Apr 2005 14:31
george wrote: > The thesis IS A PROPOSED > DEFINITION of ALGORITHM, NOT of "effectively computable > function on naturals into naturals". You're just plain wrong. -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |