Church-Turing Thesis

[Prime Monster]

Could anybody skilled in the art of mathematics explain the Church-Turing Thesis for me, or point me in the right direction?
I found the Mathworld entry for it, and I do understand the consquences, but I need it in a language a politician can understand.

PM

[garo]

Well you could do worse than picking up Hopcroft and Ullman's Introduction to Automata Theory, Languages and Computation http://www.amazon.co.uk/exec/obidos/...739820-9890850

It has a reasonably good description of Turing machines and the Church-Turing hypothesis. The first edition was a bit technical, CS undergrad level, but I'm told the second is less so.

In the meanwhile here is the short answer.

A Turing machine is an abstract construct for a machine. In the simplest form you have an infinite tape with symbols written on it and a moving read/write head that moves from cell to cell, reading and optionally overwriting a cell's contents. The input alphabet and output alphabet need to be defined for every instance of the machine and so does the set of transitions, (i.e. given the state of the machine and the contents of the cell the head is currently on, what should it do? move left, write, overwrite and if so with what), the start state and set of accepting or final states.

CT says that every computational problem can be translated into such a machine and all known real-world computations have been shown to have a TM equivalent.

[xilman]

Originally Posted by garo

CT says that every computational problem can be translated into such a machine and all known real-world computations have been shown to have a TM equivalent.

Apart from computations that rely on true randomness. There are things a QTM (quantum Turing machine) can do that a TM can not and some algorithms that take polytime on a QTM that take exptime on a TM. Simulating a QTM is one of the latter, whereas simulating any TM on any other TM can be done in polytime.


Paul

[garo]

Correct! Should have added the bit about quantum computations and QTMs. Thanks for that xilman.

I believe QTMs weren't really invented by Turing and the CT hypothesis does not deal with them at all. Correct me if I am wrong. Also how exactly is a QTM different from a non-deterministic TM?

[ColdFury]

There are things a QTM (quantum Turing machine) can do that a TM can not

A QTM can be inherently faster than a TM, but they are still computationally equivalent. A TM can do everything a QTM can do, although with possible exponential slowdown.

[xilman]

Originally Posted by ColdFury

A QTM can be inherently faster than a TM, but they are still computationally equivalent. A TM can do everything a QTM can do, although with possible exponential slowdown.

I disagree.

A non-deterministic TM may be able to do anything a QTM can do, possibly with exponential slowdown (though I've not seen a proof of this claim) but a clasical TM can not.

Consider this program: "if (random_value < 0.5) then halt else {print FOO; halt}" where random_value is chosen uniformly and at random in the range 0 .. 1.

It's clear how a QTM can be programmed so, but how do you do it with a classical TM?


Paul

[ColdFury]

A non-deterministic TM may be able to do anything a QTM can do, possibly with exponential slowdown (though I've not seen a proof of this claim) but a clasical TM can not.

A non-deterministic TM can be simulated by a classical TM by computing all the branches of the computation.

It's clear how a QTM can be programmed so, but how do you do it with a classical TM?

Your point is taken, though I argue since its not an algorithm which solves any problem, you're not really adding any additional computational power. Any algorithm which uses randomness can be simulated by a classical TM by computing every possible outcome.

[mfgoode]

A simple question deserves a simple answer
Try out this site. http://plato.stanford.edu/entries/church-turing/
Mally

[Prime Monster]

Originally Posted by mfgoode

A simple question deserves a simple answer
Try out this site. http://plato.stanford.edu/entries/church-turing/
Mally

Thank you

PM