Assignment 3

Turing Machines and Theory of Computation

Problem 1 - Calculating Remainders

Write the program for a Turing machine $M_{\%3}$ that computes the remainder of its input when divided by 3. Given, for example, an input tape containing the number 8:

executing $M_{\%3}$ should leave the number 2 on the tape, because 2 is the remainder of 8 when divided by 3.

Problem 2 - Duplicating a number

Implement a Turing machine $M_{\text{copy}}$ that copies an input value on the tape, leaving two identical values on the output separated by a single 0. Thus, if the input tape is:

the final configuration should be

Problem 3: The Busy Beaver Problem

The Busy Beaver problem asks:

What is the largest finite number of 1s that can be produced on blank tape using a Turing machine with $n$ states?

  1. Why is the Busy Beaver function for these machines well-defined?
    1. Because the number of possible Turing machines with 2 states and 2 symbols is finite.
    2. Because every Turing machine always halts eventually.
    3. Because the number of tape cells is infinite.
    4. Because the Busy Beaver function is constant for all inputs.
  2. What does the Busy Beaver problem demonstrate about the limits of computation?
    1. Some computational problems have no maximum running time.
    2. The Busy Beaver function grows faster than any computable function, so it cannot be computed in general.
    3. All Turing machines can be simulated efficiently.
    4. Infinite tapes lead to infinite step counts.

Problem 4: The Halting Problem

1) Conceptual Understanding
Which of the following best describes the Halting Problem?

  1. The problem of determining whether a program will stop running or continue forever.
  2. The process of optimizing a program so that it runs faster.
  3. The act of manually stopping a program before it finishes execution.
  4. A method for scheduling multiple programs to run without conflict.

2) Implications of the Halting Problem
Why can no general algorithm exist that solves the Halting Problem for all possible programs and inputs?

  1. Because computers do not have enough memory to store such an algorithm.
  2. Because some programs are too long to analyze completely.
  3. Because the Halting Problem is provably undecidable—any such algorithm leads to a logical contradiction.
  4. Because programmers can always modify their code to avoid halting.