TÖL203F Algorithms, Logic and Complexity
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.
- 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
- Problem 4.1 on page 44 in the textbook.
- Problem 4.2 on page 44 in the textbook.
- Problem 4.3 on page 44 in the textbook.
- Show a JFLAP version of the best known 6-state Busy Beaver machine
(see Wikipedia: "current 6-state, 2-symbol best contender")
- 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.
- 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) hi.is, January 31st, 2014.