20050707, 16:10  #1 
Aug 2002
260_{10} Posts 
ChurchTuring Thesis
Could anybody skilled in the art of mathematics explain the ChurchTuring 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 
20050707, 20:18  #2 
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/...7398209890850
It has a reasonably good description of Turing machines and the ChurchTuring 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 realworld computations have been shown to have a TM equivalent. 
20050708, 12:28  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3×3,529 Posts 
Quote:
Paul 

20050708, 13:11  #4 
Aug 2002
Termonfeckin, IE
3×919 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 nondeterministic TM? Last fiddled with by garo on 20050708 at 13:12 
20050708, 16:05  #5  
Aug 2002
2^{6}·5 Posts 
Quote:


20050708, 19:03  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10587_{10} Posts 
Quote:
A nondeterministic 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 

20050709, 00:54  #7  
Aug 2002
2^{6}·5 Posts 
Quote:
Quote:


20050711, 18:13  #8 
Bronze Medalist
Jan 2004
Mumbai,India
2^{2}×3^{3}×19 Posts 
Church Turing Thesis
A simple question deserves a simple answer Try out this site. http://plato.stanford.edu/entries/churchturing/ Mally 
20050712, 05:35  #9  
Aug 2002
2^{2}·5·13 Posts 
Quote:
PM 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Peter Montgomery's Thesis  mickfrancis  Computer Science & Computational Number Theory  3  20150625 14:32 
Turing test result  xilman  Science & Technology  13  20140610 12:26 
Separation of Church and State  rogue  Soap Box  39  20110416 21:20 
Best church sign?  Xyzzy  Lounge  6  20110213 17:11 
The cmd Turing test  cmd  cmd  113  20110206 15:46 