Cheap and Secure Web Hosting Provider : See Now

[Solved]: Simulate a regular Turing Machine with one that cannot write blanks

, , No Comments
Problem Detail: 

Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?

Asked By : buddhababe

Answered By : David Richerby

To simulate a Turing machine $M$ that can write blanks with a Turing machine $M'$ that can't, just give $M'$ an extra character in its alphabet. Whenever $M$ writes a blank, $M'$ writes this new character and, whenever $M'$ sees the blank or the new character, it does what $M$ would do if it saw the blank.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback