Jack Copeland gave an interesting lecture on the Church-Turing thesis today. The CT thesis is apparently much misunderstood. Historically, it's the claim that any algorithm can be computed by a Turing machine. But even well-respected philosophers (Jack offered quotes from Fodor, Dreyfus, etc.) sometimes label a much stronger claim - that no information-processing machine can do anything that Turing machines can't - the "Church-Turing thesis", even though neither Church nor Turing ever made such a claim. Note the difference: whereas the real version merely relates Turing machines and algorithms, the stronger version places restrictions on all information processing devices. For example, the latter version implies that no machine can solve the Halting problem. More generally, it can be seen as the claim that hypercomputation is impossible, and that standard (Turing) computation is the pinnacle of information processing. The original Church-Turing thesis made no such grand claims.
An especially extravagant elaboration was made by the Churchlands. They claimed that Turing's results entail that "a Turing machine can display any systematic pattern of responses to the environment whatsoever." Jack pointed out that this was a rather outrageous claim, since some uncomputable 'patterns of response' are perfectly systematic. Consider an environment which presents integer inputs. We can assign each Turing machine a number. Now, here is a perfectly systematic pattern of responses to this environment: the info-processor take the input n, and outputs a '1' if the nth Turing machine halts, and a '0' if it does not halt. But no computer can display this pattern of responses, or else they could solve the Halting problem (which we can prove no computer can do). So there are systematic patterns of response that no computer - i.e. Turing machine - can possibly display.
Monday, October 10, 2005
10 comments:
Visitors: check my comments policy first.
Non-Blogger users: If the comment form isn't working for you, email me your comment and I can post it on your behalf. (If your comment is too long, first try breaking it into two parts.)
Note: only a member of this blog may post a comment.
Subscribe to:
Post Comments (Atom)
Posts
You lost me at "But no computer can display this pattern of responses, or else they could solve the Halting problem". What is it that implies that a computer with such a display capablity could solve the halting problem?
ReplyDeleteWell, the Halting problem is just the problem of being able to state whether the nth Turing machine halts (for some input -- I should have included this in the environment too), for any n. So the pattern I've described just is the solution to the Halting problem.
ReplyDeletehmm..
ReplyDeletehow would a machine solve the Halting problem ?
I also think it is a bit trivial to prove a turing machine can't calculate every systematic pattern.
I am thinking of somthing like - "it can't calcuate its own pattern plus 1" or somthing like that.
not sure If I understand the halting problem but it seems to have a bit of that aspect to it anyway.
I thought it was a confessional version of the Turing test. So far AI always prescribes too many Hail Mary's for some reason.
ReplyDeleteIf systematic response means computable by algorithm in a finite time, then Turing machines can indeed display any systematic pattern of responses to the environment whatsoever.
ReplyDeleteIf any of the Turing machines in your example cannot be shown to halt in a finite time by a Turing machine algorithm, then they cannot be said to halt by a non-Turing machine either.
True, we don't know that a non-algorithmic system can be simulated by a TM, but I wouldn't label a non-algorithmic machine as systematic.
But surely "systematic" does not merely mean "computable". There are uncomputable response patterns that are nevertheless perfectly systematic, as in the example (Halting responses) I provided in the main post.
ReplyDelete"If any of the Turing machines in your example cannot be shown to halt in a finite time by a Turing machine algorithm, then they cannot be said to halt by a non-Turing machine either."
ReplyDeleteWhat makes you think that? The Halting problem is solvable by hypercomputation. An example of hypercomputation would be Accelerated Turing Machines, which can conduct infinitely many processes in a finite amount of time (because each step takes only half as long as the one before: if the first step takes 1 second, then it will have completed infinitely many steps by the time the 2nd second has passed). While such machines may be physically implausible, they do seem at least logically possible. The extra-strong "Church-Turing thesis" (which, recall, neither Church nor Turing ever asserted) entails the impossibility of all such machines. But such a strong assertion is entirely unwarranted. No-one has ever proved hypercomputation impossible. In particular, Turing most certainly didn't.
> No-one has ever proved hypercomputation impossible.
ReplyDeleteYou would have to ignore at least several currently believed to be fundimental laws of the universe to allow your "ATM". Meaning that there is almost nothing in the universe we are more sure about than that there is no Accelerated Turing Machine even if you can say it has not been "proven".
Secondly I propose the machine might, effectively, only be trivially different from a turing machine that existed forever because you are just changing your units of time (or frame of reference).
I dont know about the other versions but I am concerned they too will be imposible (or more technically - should rationally be assumed to be imposible) on similar grounds.
*waits for his audiences eyes to glaze over*
If a machine can solve the Halting problem, then it really does have the power of an oracle. In regard to mathematical problems, it would be omniscient. ATM's bypass the Halting problem by making halting irrelevant because executing an infinite number of computational steps (and using infinite computational resources) is not a problem for them. While I agree that their existence isn't ruled out by CT, I can't help thinking that ATM's are cheating!
ReplyDeleteI also wonder whether a world which admits these ATM infinite computing bubbles would suffer from new forms of undecidability.
It is hard to call others' claims "outrageous" and "extravagant", I think, when one's own concept of a machine involves a machine that can carry out an infinity of discrete steps as a part of its own "computation".
ReplyDeleteAndrew Hodges, the biographer of Turing and an acknowledged expert, has dismantled Copeland's historical claims about Turing and the Thesis, referring to them as "sensational", and further referring to one of Copeland's ideas for "hypercomputation" as "the most ludicrous proposal ever aired in Scientific American".