CSE396 Problem Set 10 Answer Key Spring 2017
The Final Exam is set for Tuesday, May 16 in the lecture room, Cooke 121, 11:45am{
2:45pm. We have decided to repeat the terms used for last year’s exam in the identical
ro
...
CSE396 Problem Set 10 Answer Key Spring 2017
The Final Exam is set for Tuesday, May 16 in the lecture room, Cooke 121, 11:45am{
2:45pm. We have decided to repeat the terms used for last year’s exam in the identical
room: one notes binder is allowed. The textbook is not allowed, and all electronic devices are
forbidden. If you must bring a backpack or other bulky bag into the room at all, it must be
stowed along the side of the room. [Plus note the Review Session on Monday 5/15 from
12:00{1:50pm in NSC 228; graded PS10s will be returned there and in my 2{4pm office
hours back in Davis afterward.]
(1) Consider the following decision problem:
Exception Throw
Instance: A Java program P and an input stream x 2 ASCII ∗.
Question: Does running P on x throw an ArrayIndexOutOfBoundsException?
Show that this decision problem is undecidable|by arguing concretely that if it were decidable, then the Acceptance Problem for Turing machines would be decidable, which it isn’t. (It
may help you to know that the Turing Kit program, though it has other bugs, never throws
this exception. 18 pts.)
Answer: Given a TM M and an argument w to M, define a Java program P as follows: P
is the \Turing Kit" program (or JFLAP or some other Turing machine simulator) with two
modifications:
• It has M and w embedded in its code, so that when P starts up on any input x (which
is ignored) it begins a simulation of M on input w.
• Right after the line that displays the \String accepted" dialog, it has a line that throws
the exception|which importantly is the only way that exception can be thrown when
running P
[Show More]
.png)
.png)
.png)
