mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-07-07, 16:10   #1
Prime Monster
 
Prime Monster's Avatar
 
Aug 2002

22×5×13 Posts
Question 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
Prime Monster is offline   Reply With Quote
Old 2005-07-07, 20:18   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

2×5×251 Posts
Default

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.
garo is offline   Reply With Quote
Old 2005-07-08, 12:28   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

7·1,447 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-07-08, 13:11   #4
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

1001110011102 Posts
Default

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
garo is offline   Reply With Quote
Old 2005-07-08, 16:05   #5
ColdFury
 
ColdFury's Avatar
 
Aug 2002

32010 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2005-07-08, 19:03   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

7×1,447 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-07-09, 00:54   #7
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2005-07-11, 18:13   #8
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

80416 Posts
Cool Church Turing Thesis


A simple question deserves a simple answer
Try out this site. http://plato.stanford.edu/entries/church-turing/
Mally
mfgoode is offline   Reply With Quote
Old 2005-07-12, 05:35   #9
Prime Monster
 
Prime Monster's Avatar
 
Aug 2002

4048 Posts
Default

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
Prime Monster is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Peter Montgomery's Thesis mickfrancis Computer Science & Computational Number Theory 3 2015-06-25 14:32
Turing test result xilman Science & Technology 13 2014-06-10 12:26
Separation of Church and State rogue Soap Box 39 2011-04-16 21:20
Best church sign? Xyzzy Lounge 6 2011-02-13 17:11
The cmd Turing test cmd cmd 113 2011-02-06 15:46

All times are UTC. The time now is 14:43.

Thu Oct 29 14:43:45 UTC 2020 up 49 days, 11:54, 2 users, load averages: 2.31, 1.98, 1.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.