HPS 0628 | Paradox | |
Back to doc list
1a. Compare the number of steps needed for task of size n by a quadratic algorithm that requires 1,000n2 steps versus an exponential algorithm that requires 10n 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,000n2 versus an exponential algorithm that requires 10n 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.)