CSE396 Problem Set 10 Answer Key Spring 2018
(1) Answers revealed on TopHat. Please read and study the paragraph-length explanations
for each question.
(2) The Turing Kit shows Turing machine tapes that are infinite i
...
CSE396 Problem Set 10 Answer Key Spring 2018
(1) Answers revealed on TopHat. Please read and study the paragraph-length explanations
for each question.
(2) The Turing Kit shows Turing machine tapes that are infinite in both directions but other
sources stipulate a sharp left edge at cell 0. Some of those sources say that an attempted left
move in cell 0 becomes a stay move, but let us say instead that the TM then hangs. There
is a simple way to simulate a virtual two-way infinite tape by a one-way infinite tape that is
guaranteed not to hang: implement cell +m on Turing Kit as cell 2m and cell −m as cell
2m − 1. Every time the Turing Kit machine moves a head R move your head R twice and
similarly translate L to L twice, unless the move crosses cell 0, in which case you give-ortake an extra step to shift between the \odd track" and the \even track." There is only a
roughly-factor-of-2 time slowdown.
Nevertheless, a Turing machine with one-sided tapes that isn’t doing this emulation can
still hang. It’s a reasonable metaphor for real-world \hangs"|where unlike an infinite loop,
you know immediately that something has gone wrong. We’d like to make both our Turing
machines and our device drivers hang-free, but. . . So we have this decision problem:
• Instance: A Turing machine M coded for a single one-way-infinite tape.
• Question: Does there exist an input x such that M(x) hangs?
Prove by reduction from any of ATM, KTM, or NETM (your choice) that this problem is
undecidable. Show also that its language is computably enumerable. (Hints: A technical
detail which you should reference in your proof: there is a guaranteed no-hang universal Turing
machine U that the machine M0 you create in your reduction can call for the \Simulate M
on. . . " body of your code. Your M0 will have other code that could be accompanied by the
Kingston Trio recording of \Tom Dooley" [you can Google that]. 18 + 6 = 24 pts.)
[Show More]