SUNY Buffalo State College_CSE 396_CSE396ps10key-REVIEWED AND EDITED BY EXPERTS

Document Content and Description Below

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]

Last updated: 1 year ago

Preview 1 out of 4 pages