mersenneforum.org > Math Church-Turing Thesis
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-07-07, 16:10 #1 Prime Monster     Aug 2002 4048 Posts Church-Turing Thesis 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
 2005-07-07, 20:18 #2 garo     Aug 2002 Termonfeckin, IE 3·919 Posts 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.
2005-07-08, 12:28   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22·3·877 Posts

Quote:
 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

 2005-07-08, 13:11 #4 garo     Aug 2002 Termonfeckin, IE AC516 Posts 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? Last fiddled with by garo on 2005-07-08 at 13:12
2005-07-08, 16:05   #5
ColdFury

Aug 2002

26·5 Posts

Quote:
 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.

2005-07-08, 19:03   #6
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

22×3×877 Posts

Quote:
 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

2005-07-09, 00:54   #7
ColdFury

Aug 2002

14016 Posts

Quote:
 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.

Quote:
 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.

 2005-07-11, 18:13 #8 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22×33×19 Posts Church Turing Thesis A simple question deserves a simple answer Try out this site. http://plato.stanford.edu/entries/church-turing/ Mally
2005-07-12, 05:35   #9
Prime Monster

Aug 2002

1000001002 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Computer Science & Computational Number Theory 3 2015-06-25 14:32 xilman Science & Technology 13 2014-06-10 12:26 rogue Soap Box 39 2011-04-16 21:20 Xyzzy Lounge 6 2011-02-13 17:11 cmd cmd 113 2011-02-06 15:46

All times are UTC. The time now is 11:45.

Wed Jan 27 11:45:08 UTC 2021 up 55 days, 7:56, 0 users, load averages: 4.95, 4.66, 4.75