Cheap and Secure Web Hosting Provider : See Now

[Solved]: What's the error in the following proof of the halting problem decidability?

, , No Comments
Problem Detail: 

Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. Now let's apply any known algorithm for searching a cycle in the chain of pointers to that function and we've got it!

P.S. Sorry, it's late night question... The proof has to be complete nonsense :-)

Asked By : Andrew Zabavnikov

Answered By : Andrej Bauer

A Turing machine may run forever without ever entering any kind of cycle. (Consider the machine which always just moves its head to the right.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45670

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback