Back to doc list

Assignment 13.
Uncomputable Tasks 1

1a. Compare the number of steps needed for task of size n by a quadratic algorithm that requires 1,000n² steps versus an exponential algorithm that requires 10ⁿ steps. When do the demands of the exponential algorithm first exceed

1b. Compare the number of steps needed for task of size n by a quadratic algorithm that requires 10,000n² versus an exponential algorithm that requires 10ⁿ steps. When do the demands of the exponential algorithm first exceed those of the quadratic?

2. 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?

3. 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.)