Problem Solving in Automata, Languages, and Complexity

5

Computability Theory

5.1 Universal Turing Machines

In this chapter, we study the general properties of computable functions and
develop some basic proof techniques for proving the computability or noncom-
putability results of given problems. This theory of computability is presented
in the Turing machine model. Based on the Church-Turing Thesis, however,
it is, in general, independent of the particular machine model chosen. In par-
ticular, we will present a few basic properties of the Turing machine model
and demonstrate that the computability theory of any programming system
which has these properties remains the same.
We start with the first basic property of the Turing machine system: the
enumerability of Turing machines. We fix a class M of two-way infinite one-
tape DTM’s, which has the following common form:
(1) The states of a DTM in M are 41,.. .,Q~, for some n > - 1.
(2) The initial state is 41 and the final state is qn.
(3) The input alphabet is { 0, 1).
(4) The tape alphabet is {al, ~2,... , a,}, m. - > 3, with al = 0, a2 = 1 and
a3 = B.
For every finite alphabet C with t elements, we can encode a symbol in
C by a string x in (0, l} of length [log2 tl. (It is like using a byte or a
word to encode a symbol.) For any string x in C, we write 5 to denote
the string in (0, 1}* that encodes the string x: symbol by symbol. It is not
225

Problem Solving in Automata, Languages, and Complexity.

Ding-Zhu Du, Ker-I Ko

Copyright2001 by John Wiley & Sons, Inc.

ISBNs: 0-471-43960-6 (Hardback); 0-471-22464-2 (Electronic)