Mathematical Foundations of Computer Science

COMPSCI 350 FC 2006

COMPSCI 350

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

CLOSURE THEOREMS FOR THE CLASS OF TURING-DECIDABLE AND FOR THE CLASS OF TURING-RECOGNISABLE LANGUAGES.

Theorem 3 [First Closure Theorem]

The class of Turing-decidable languages over a fixed alphabet is closed under the operations of i) union, ii) intersection, iii) complement, iv) concatenation, and v) star.

Proof of Theorem 3:

i) Suppose A and B are Turing-decidable. Let M1 decide A and M2 decide B. Then M decides AB, where M is as follows:

M = “On input w,

1. Make a second copy of w. Run M1 on the first copy of w. If M1 accepts, accept. If M1 rejects, clear the tape apart from the second copy of w, and go to 2.
2. Run M2 on the second copy of w. If M2 accepts, accept. Otherwise, reject.”

Clearly, M accepts w iff either M1 or M2 accepts w, ie, iff w is in AB.

ii) Suppose A and B are Turing-decidable. Let M1 decide A and M2 decide B. Then M decides AB, where M is as follows:

M = “On input w,

1. Make a second copy of w. Run M1 on the first copy of w. . If M1 accepts, go to 2. If M1 rejects, reject.
2. Run M2 on the second copy of w. If M2 accepts, accepts. Otherwise, reject.”

Clearly, M accepts w iff both M1 and M2 accept w, ie, iff w is in AB.

iii) Suppose A is Turing-decidable. Let M decide A. Then M’ decides the complement of A:

M’ = “On input w,

1. Run M on w.
2. If M accepts, reject. If N rejects, accept.”

Clearly, M’ is a decider (since M is) and M accepts w iff M rejects w iff w is in the complement of A. Hence M’ decides the complement of A.

iv) Suppose A and B are Turing-decidable. Let M1 decide A and M2 decide B. Then N, a NTM, decides AB [the concatenation of A and B], where N is as follows:

M = “On input w,

1. Nondeterministically split w into two parts, x and y. Go to 2.
2. Run M1 on the left part, x. If M1 accepts, go to 3. If M1 rejects, go to qreject.
3. Run M2 on the right part y. If M2 accepts, go to qaccept. If M2 rejects, go to qreject.”

Clearly N accepts w just so long as w is the concatenation of two strings x and y, the first of which is in A and the second in B, and N rejects w otherwise. Hence N decides AB. By the corollary to Theorem 2, AB is Turing decidable.

v) Suppose A and B are Turing-decidable. Let M decide A. Then N, a NTM, decides A*, where N is as follows:

M = “On input w,

1.If w = , go to qaccept. Otherwise, nondeterministically split A into k parts (0<k≤|w|). Go to 2.

2.Run M on each of these parts. If M accepts each of them, go into qaccept. If M rejects any of them, go into qreject.”

It is not hard to see that M accepts an input w just so long as w is the concatenation of k strings, m ≤ |w|, all of which are in A. Furthermore, N is a decider, so that, by the corollary to Theorem 2, A* is Turing-decidable.

Theorem 4 [Second Closure Theorem]

The class of Turing-recognisable languages over a fixed alphabet is closed under the operations of i) union, ii) intersection, iii) concatenation, and iv) star.

Proof of Theorem 4:

i) Suppose A and B are Turing-recogisable. Let M1 recognise A and M2 recognise B. Then M recognises AB, where M is as follows:

M = “On input w,

1.Make a second copy of w, and run M1 and M2 alternatively on the two copies of w, one step at a time. If either accepts, accept. If both machines reject [ie, go into qreject], reject.”

Clearly, M accepts w iff either M1 or M2 accepts w, ie, iff w is in AB. Note that if neither M1 nor M2 accept or reject w, then M will loop.

ii) Suppose A and B are Turing- recognisable. Let M1 recognise A and M2 recognise B. Then M recognises AB, where M is as follows:

M = “On input w,

1.Make a second copy of w, and run M1 and M2 alternatively on the two copies of w, one step at a time. If both accept, accept. If either machine rejects [ie, goes into qreject], reject.”

Note that neither M1 nor M2 are guaranteed to be deciders, so this machine M may never halt. In any case, it is clear that M accepts w just in case both M1 and M2 accept w, ie w is in both A and B.

iii) Suppose A and B are Turing- recognisable. Let M1 recognise A and M2 recognise B. Then N, a NTM, recognises AB, where N is as follows:

M = “On input w,

1.Nondeterministically split w into two parts, x and y. Go to 2.

2.Run M1 and M2 alternatively on the two parts x and y of w, one step at a time. If at any point both parts are accepted, accept, ie go into qaccept. If at any point one part is rejected, go into qreject.”

Once again, neither M1 nor M2 are guaranteed to be deciders, so this machine M may never halt. In any case, it is clear that M accepts w just in case w is the concatenation of two strings x and y such that M1 accepts and M2 accept w, ie such that x is in A and y is in B.

iv) Suppose A is Turing-recognisable. Let M recognise A. Then N, a NTM, recognises A*, where N is as follows:

M = “On input w,

1.If w = , go to qaccept. Otherwise, nondeterministically split A into k parts (0<k≤|w|). Go to 2.

2.Run M alternatively on each of these parts, one step at a time. If at some point M has accepted each of them, go into qaccept. If M rejects any of them, go into qreject.”

It is not hard to see that N accepts an input w just so long as w is the concatenation of k strings, 0 ≤ k ≤ |w|, all of which are accepted by M and hence are in A.

It is easy to see that the proof of the closure of Turing-decidability can’t be adapted to the case of Turing-recognisability. Indeed, it can be proved that the class of Turing-recognisable languages is not closed under complementation. This is a corollary of the undecidability of the Halting Problem for Turing machines.

------

ENCODING TURING MACHINES AND A UNIVERSAL TURING MACHINE.

By a standard TM we mean a deterministic TM with a single tape that is infinite to the right only. Each standard TM has 7 components, Q, , , , qstart , qaccept , qreject . Since Q, , and  are finite, we could write these as as strings using the symbols in Q, , and and with parentheses, commas, and so on, as punctuation. But the set of all such strings would not then be a language over a single alphabet, since machines may have arbitrarily large state sets and tape alphabets. Instead, we must encode the states and symbols over a fixed alphabet.

To do this, we adopt certain conventions, without loss of generality. Assume that there are fixed countably infinite sets Q= {qaccept , qreject , q1, q2, q3, ...} and  = {a1, a2, a3, ...}, such that for every Turing machine, the state set is a finite subset of Qand the tape alphabet (and hence also the input alphabet) is a finite subset of We can take the blank symbol U to be a designated member of , say a1. In addition, let the start state of every machine be the state q1.

We adopt the following correspondence g between the component symbols of a Turing machine and strings over the one-symbol alphabet {I}, which .

 g()

Note that no two members of Qare represented in the same way, nor are any two member of , nor, of course, are L and R. (We could have assigned Ii rather than Ii+2 to aI [there would have been no ambiguity] but chose to make the method of assignment to the alphabet-symbol exactly the same as for the state-symbols.)

We encode Turing machines by using the 2-symbol alphabet {c, 1}. Suppose M is a Turing machine (Q, , , , q1 , qaccept , qreject ), where
Q  Qand  In that case, Q can be written as
{qi1, qi2, qi3, ..., qik} (where i1 < i2 < ... < ik) and  as
{aj1, aj2, aj3, ..., ajl } (where j1 < j2 < ... < jl). Note that since q1 is the start state for all machines, qi1, is always q1. Similarly,  can be written as {at1, at2, at3, ..., atm }. We can encode the different parts of the machine in terms of strings of c and I’s as follows:

<Q> = cg(qi1)cg(qi2)c ...cg(qik)c,

<> = cg(at1)cg(at2)c ...cg(atm)c,

<> = cg(aj1)cg(aj2)c ...cg(ajl)c.

We can also define the encoding of the start state, < q1 >, as g(q1), ie III, and similarly for <qaccept > and <qreject >. (Since we are taking the start state q1 and the two halting states qaccept and qreject as fixed for all machines, these encodings don’t play a significant role.)

To define <> , we first define kl strings, Opr (call them transition strings), with 1≤ p ≤ k and 1 ≤ r ≤ l (there are kl strings since there are kl arguments for , one for each state-symbol pair). Given p and r, such a transition string encodes the operation of the transition function  on the state-symbol pair (qip , a jr ).

If we let  (qip , ajr ) = (qt, am, R), say, then we set Opr = cw1cw2cw3cw4cw5c , where w1 = g(qip), w2 = g(ajr), w3 = g(qt), w4 = g(am), and w5 = g(R).

(Example a: If M = (Q, , , , q1 , qaccept , qreject ), where
Q = {qaccept , qreject , q1},  = {a2, a5 , a7}, and  is as follows:
i)  (q1 , a 2) = (q1, a5, R),
ii)  (q1 , a 5) = (qreject, a5, R), and
iii)  (q1 , a 7) = (qaccept, a5, R)
then we have the following three transition strings O11 , O12, and O13, corresponding to i) — iii):

O11 = cI3cI4cI3cI7cI2c,
O12 = cI3cI7cI2cI7cI2c,
O13 = cI3cI9cIcI7cI2c.

These define the workings of the transition function.)

Finally, we can write <> for a string that defines the entire transition function:

cO11O12 ... O1l O2lO22 ... O2l...Ok1Ok2 ...Oklc

(Note that the encoding of the function of Example a is:

ccI3cI4cI3cI7cI2ccI3cI7cI2cI7cI2ccI3cI9cIcI7cI2cc.)

We can now define the encoding of machine M, < M >, as follows:

< M > = c<Q>c<>c<>c<>c<q1>c<qaccept >c<qreject >c

(as before, given that q1, qaccept, and qreject are fixed for all machines, their encodings don’t play a distinctive role, and we could have done without them when encoding machines).

We now construct a Universal Turing machine U. This machine will use the encodings <M> of Turing machines as programs which it will then simulate on certain inputs w to those other machines. Note that such inputs w will also be provided to U in encoded form, as follows. If w = w1...wn, where each wi   (and hence wi  ), then <w> = cg(w1)c... cg(wn)c. In order for U to simulate the working of M on w, it receives as input <M,w>, the concatenation of <M> and <w>.

Theorem 5 There is a universal Turing machine U (over the language  = {c, I}) such that, presented with <M,w> as input, where M is a Turing machine and w a string over  U halts in the accept state if M accepts w, halts in the reject state if M rejects w, and doesn’t halt if M doesn’t halt on w.

Proof: We construct a universal Turing machine U that is actually a three-tape machine, but since we know that every multitape machine can be simulated by a standard one-tape TM, we know that there is a standard TM that is equivalent to U (ie, accepts what U accepts, rejects what U rejects, and doesn’t halt when U doesn’t halt). The machine uses its three tapes as follows. The first tape contains the encoding of what is on M’s tape, the second tape contains the encoding of M itself (ie, <M>) and the third tape contains the encoding of the state of M at the current point in the simulated computation.

The machine is started with some string <M,w> on its first tape and the other tapes blank. U then first moves <M> onto the second tape, and moves <w> to the left of the first tape. (Note that U can easily determine where <M> ends and <w> begins.) U then copies the encoding of the start state q1 of M (that is, the string I3) to the third tape. U first determines whether w is a string over the input alphabet of M. If it isn’t, it enters qreject. If it is, U begins simulating the steps of the computation of M on w on the first tape. Between such simulated steps, U keeps the heads on the second and third tapes at the left ends of those tapes, and the head on the first tape scanning the c that begins the encoded version of the symbol that M would be scanning at the corresponding time.

U now finds on its second tape a block of the form ccIicIjcIkcIlcImcc (representing a transition) such that Ii is the string of I’s on the third tape (encoding the state qi-2 that M is in), and Ij is the string to the right of the current head position on the first tape (encoding the symbol aj-2 that M would be scanning at this stage). U then changes the first tape accordingly, replacing Ij with Il, and moving left or right to the preceding or next block of I’s depending on whether m is 1 or 2 (ie, depending on whether Im represents the move L or R). U also puts Ik on the third tape, checking to see whether this is the encoding of state q accept or of qreject .(by checking to see if k = 1 or 2). If it is, U halts in the appropriate state, ie, in qaccept if k = 1 and qreject.if k = 2. If the third tape does not contain the encoding of a halting state, U simulates another computational step by M.

By construction, U accepts <M, w> if M accepts w; rejects <M, w> if M rejects w; and doesn’t halt on <M, w> if M doesn’t halt on w.

Definition 8 Given sets A and B, we say that

(i) A and B are equivalent (or: have the same cardinality or the same size) iff there is a bijective function f: A  B. (We sometimes also call such a function a [one-one] correspondence [between A and B].)

(ii) A is finite iff either A is empty or is equivalent to {1, , n} for some natural number n.

(iii) A is infinite iff A is not finite.

(iv) A is countable iff either A is finite or is equivalent to N (where N = the set of natural numbers {1, 2, …}.

(v) A is countably infinite iff A is countable and infinite.

(vi) A is uncountably infinite iff A is infinite but not countable.

Theorem 6 a) The set of all Turing machines with input alphabets   is countably infinite;

b) the set of all Turing-recognisable languages over alphabets  is countably infinite.

Proof: a) Consider all encodings <M> of Turing machines. Replace ‘c’ by ‘2’ and ‘I’ by ‘1’. Then every such encoding <M> becomes a string of 1s and 2s, and so represents a unique natural number in decimal notation. Call this the number code of such a <M>. Only some natural numbers will be codes of the relevant machines, of course. Let m1 be the smallest such number, m2 the next smallest such number, and so on. Then we can let M1 be the machine with number-code m1, M2 be the machine with number-code m2, and so on. Hence the set of all such machines is countably infinite (ie, the same size as N): just take the function f(Mi) = i, which is clearly one-one and onto.

b) Consider the sequence of languages (M1), (M2), ..., where (Mi), is the language recognised by Mi (the i-th machine in our listing of Turing machines). By removing languages from this sequence that have already occurred earlier in this sequence, w obtain a non-repeating sequence L1, L2, L3, ... of all and only Turing-recognisable languages. This shows that the set of all such languages is countably infinite.

(Similarly, by restricting machines M to machines with a fixed alphabet   , the same proof shows that the set of all Turing machines over input alphabet  and the set of all Turing-recognisable languages  are both countably infinite.)

Theorem 7. The class of all languages (over some alphabet ) is uncountably infinite.

Proof: Consider the set of all strings of length n. It is easy to prove, by induction, that there are ||n of these. We can now list all strings of length 0, then of length 1, then of length 2, etc, in standard lexicographic order as follows. Assume that we have a certain listing of the symbols of , so that we can talk about the first, second, etc, symbol of . We say that string v precedes string w in this lexicographic order if, for some j, the j-th symbol of v comes before the j-th symbol of w and for all i< j, the i-th symbol of v is the same as the i-th symbol of w. Let the listing of all strings over be w1, w2, w3, w4, .... Hence the class of all strings or words over  is countably infinite.

Now suppose, contrary to what we are trying to establish, that the class of all languages (over ) is countably infinite. Then we have a (one-one) correspondence between the class of all such languages and {1, 2, 3, }. For arbitrary n, let Ln be the language corresponding to n in this correspondence. We now construct a new language L as follows:

(*)For each i ≥ 1, put wi in L iff wi  Li
(i.e., wi  L iff wi  Li

By construction, L is a language over and so L = Lk for some k  1. Then we can derive a contradiction as follows:
Either wk  Lk or wk  Lk. If wk  Lk, then since Lk = L it follows from (*) that wk  Lk. But if wk  Lk then, again by (*), wk  L and so wk  Lk after all (since L = Lk).

Hence the assumption that the class of all languages over  is countably infinite results in a contradiction. It follows that the class of all languages over  is not countably infinite. Since it is certainly infinite, it must therefore be uncountably infinite.

Corollary: We already know from Theorem 6 that the class of all Turing-recognisable languages (over ) is only countably infinite. It immediately follows that there are languages over  that are NOT Turing-recognisable.