Computability - Models of Computation: Exploring the Power of Computing - page 223

A

order of the next letter. For example, for the alphabet and the ordering given on its letters,

201021 < 201200.
A simple algorithm produces the strings over an alphabet in lexicographical order. Strings
of length 1 are produced by enumerating the letters from the alphabet in increasing order.
Strings of length n are enumerated by choosing the first letter from the alphabet in increasing
order. The remaining n

−

1 letters are generated in lexicographical order by applying this
algorithm recursively on strings of length n

−

1.
To prepare for later results, we observe that it is straightforward to test an arbitrary string
over the alphabet Λ giveninDefinition 5.5.1 to determine if it is a canonical description ρ ( M )
of a Turing machine M . Each must be contained in ([( <

# 1 ∗ > ) 3 ]) ∗ and have
a transition for each state and tape letter. If a putative encoding is not canonical, we associate
with it the two-state null TM T null with next-state function satisfying δ ( s , a )=( h , a ) for all
tape letters a . This encoding associates a Turing machine with each string over the alphabet Λ .
We now show how to identify the j th Turing machine , M j . Given an order to the
symbols in Λ , strings over this alphabet are generated in lexicographical order. We define the
null TM to be the zeroth TM. Each string over Λ that is not a canonical encoding is associated
with this machine. The first TM is the one described by the lexicographically first string over
Λ that is a canonical encoding. The second TM is described by the second canonical encoding,
etc. Not only does a TM determine which string is a canonical encoding, but when combined
with an algorithm to generate strings in lexicographical order, this procedure also assigns a
Turing machine to each string and allows the j th Turing machine to be found.
Observe that there is no loss in generality in assuming that the encodings of Turing ma-
chines are binary strings. We need only create a mapping from the letters in the alphabet Λ
to binary strings. Since it may be necessary to use marked letters, we can assume that the 20
strings in Λ are available and are encoded into 5-bit binary strings. This allows us to view
encodings of Turing machines as binary strings but to speak of the encodings in terms of the
letters in the alphabet Λ .

{

0, 1, β , L , R

}

5.7 Limits on Language Acceptance
A language L that is decidable (also called recursive ) has an algorithm, a Turing machine
that halts on all inputs and accepts just those strings in L . A language for which there is a
Turing machine that accepts just those strings in L , possibly not halting on strings not in L ,
is recursively enumerable . A language that is recursively enumerable but not decidable is
unsolvable .
We begin by describing some decidable languages and then exhibit a language,

L 1 ,that
is not recursively enumerable (no Turing machine exists to accepts strings in it) but whose
complement,

L 2 , is recursively enumerable but not decidable; that is, L 2 is unsolvable. We use

L 2 to show that other languages, including the halting problem, are unsolvable.

the language

5.7.1 Decidable Languages
Our first decidable problem is the language of pairs of regular expressions and strings such that
the regular expression describes a language containing the corresponding string:

L RX = { R , w | w is in the language described by the regular expression R }