TL203F Algorithms, Logic and Complexity

Homework 5

We have looked at functions that can not be computed by a Turing machine. This is the contents of Chapter 4 of the book. We covered the whole chapter, except the proof that the busy beaver function in uncomputable. Next week we will start on Abacus machines.


  1. On page 36 of the textbook we saw that the smallest numbers representing valid Turing machines are 210 (or (1, 1, 1, 1)), 420 (or (2, 1, 1, 1)), and 630 (or (1, 2, 1, 1)). What are the next two numbers that represent valid Turing machines? Remember that the T.M. has to be in the canonical form that is described on the page (i.e. have a halting state, all transitions present, ...).

    1. Problem 4.1 on page 44 in the textbook.
    2. Problem 4.2 on page 44 in the textbook.

  2. Problem 4.3 on page 44 in the textbook.

  3. Show a JFLAP version of the best known 6-state Busy Beaver machine (see Wikipedia: "current 6-state, 2-symbol best contender")

    1. Show that if we have a Turing machine MBB that computes the Busy Beaver function then we could solve the Halting problem for Turing machines that start with an empty tape.
    2. How could we use a solution to the Halting problem on an empty tape to solve the general Halting problem, i.e. deciding if Turing machine Mm halts on input n?

Hand this homework in before 12:00 on friday February 7th.

hh (hja), January 31st, 2014.