0
$\begingroup$

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

|cite|improve this question
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ If that is indeed the desired answer, it's a rather boring technical exercise. More interesting would be, "can not write symbols not in the input alphabet". $\endgroup$ – Raphael♦ Nov 5 '14 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.