Back to doc list

Assignment 11.
Uncomputable Tasks

1. The initial tape for a Turing machine is

... blank blank B B B B B B B blank blank ...

The head is programmed as
1 B blank R 1
and is located initially on the leftmost "B". What is the effect on the tape of the running of the program? Will the machine halt? How will that happen?

2. If a Turing machine is initialized with a blank tape, devise a program that will write the symbol A in five successive cells and then halt. (Hint: have one line for each time A is written.)

3. Here is an attempt to solve the halting problem. For a given target program with a given input, the solver program just simulates step by step what the target program does. If it halts report that. If it goes into an infinite loop of repeated states, report that.

3a. If this program were to function as plan, how would it violate the impossibility in the halting problem?

3b.  How does this solution fail?