TOC Chapter 11

Chapter 11. Universal Turing Machine and Decidability

In this chapter, we consider universal turing machine (TM), the halting problem, and the concept of undecidability.

11.1. Encoding and Enumeration of Turing Machines

The TM is specified by a 6-tuple M = (K, Σ, Γ, δ, q₀, F) (refer Definition 9.1). in Γ is a special symbol. The TM can be encoded as a binary string. Without loss of generality, we can take the state set as (q₁,q₂, ..., q_s} where q₁ is the initial state and q₂ is the final state. The tape symbol set can be taken as {,0,1}. A move of the TM is represented as:

δ(q_i, X_j) = (q_k, X_r, d_l)

11.2. Recursive and Recursively Enumerable Sets

We have seen that the language accepted by a TM is a type 0 language. It is also called a recursively enumerable (RE) set. A TM accepts a string by going to a final state and halting. It can reject a string by halting in a non-final state or getting into a loop. A TM when started on an input may get into a loop and never halt.

We have also seen that a TM corresponds to an effective procedure. An effective procedure is one where at each step, the next step is specified. An effective procedure need not halt. For example,

11.3. Universal Turing Machine

A Universal TM is a TM which can simulate any other TM including itself. Let us denote a universal TM by U. Without loss of generality, we are considering TMs with tape alphabets {0,1,}. The encoding of such a TM T is a binary string d_T. U has three tapes. The first tape is presented with d_T t; i.e., the encoding of T and the input t to T. It will be of the form:

111	...	11	...	...	111 t	...

11.4. Problems, Instances, and Languages

A decision problem is a problem for which the answer is ‘yes’ or ‘no.’ For example, satisfiability problem means to find out whether a Boolean expression is satisfiable or not. We call this as SAT. Also AMB is the ambiguity problem for CFG – i.e., finding out whether a CFG is ambiguous or not. A particular CFG is an instance of the problem. If this particular CFG G is ambiguous, it is an ‘yes’ instance of the problem. If it is not ambiguous, it is a ‘no’ instance of the problem. Similarly, a particular Boolean expression is an instance of SAT problem. If it is satisfiable, it is an ‘yes’ instance of the problem. If it is not satisfiable, it is a ‘no’ instance of the problem. In contrast to these problems, problems like finding a Hamiltonian circuit in a graph are called optimization problems. Whether a graph has a Hamiltonian circuit or not is a decision problem. Finding one is an optimization problem. We shall consider more of this concept in the next chapter.

Any instance of a problem can be encoded as a string. A Boolean expression can be looked at as a string. For example, (x₁ + x₂)(₁ + ₂) can be written as (x1 + x2)(¬ x1 + ¬ x2) – a string from the alphabet {(,), x, +, ¬, 0,1,..., 9}. A CFG G = (N, T, P, S) can be looked at as a string over N∪T∪{(,), {,}, →,}. For example, the grammar ({S}, {a, b}, P, S) where P consists of S → aSb, S → ab can be looked at as a string ({S}, {a, b}, {S → aSb, S → ab}, S). It is to be noted that generally integers are represented as decimal or binary and not as unary. The problem can be re-formulated as one recognizing the language consisting of the ‘yes’ instances of the problem.

11.5. Rice’s Theorem

Let us recall that a language accepted by a TM is called a recursively enumerable (RE) language. Without loss of generality we consider TMs over the input alphabet {0, 1} and tape alphabet {0,1,}.

Let F be a set of RE languages. Each language is over the alphabets {0, 1}. F is said to be a property of the RE languages. A language L has the property F, if L ∊ F. For example, F may denote the set {L|L is recursive}. F is a trivial property if F is empty or F contains all RE languages. Let L_F denote the set {d_M|L(M) is in F} where M is a TM, L(M) is the language accepted by it and d_M is the encoding of M.

11.6. Reduction of Problems to Show Undecidability

In the last section, we have shown that any non-trivial problem of RE sets is undecidable. This theorem helps to prove many problems to be undecidable. Consider the problem: ‘Will a TM started on a blank tape halt?’ This is equivalent to the problem does ε ∊ T(M)? and hence undecidable by Rice’s theorem. But for problems about TMs, there is no simple theorem which can be applied. Each problem has to be looked at separately.

Example 11.1.

Consider the question, “Does machine T ever print the symbol S₀ when started on tape t?” This is undecidable. There does not exist a TM which will take d_Tt as input and say whether the symbol S₀ will be printed or not, for all (T, t).

For, we may take each machine T which does not ordinarily use the symbol S₀ and alter the machine so that before it halts, ‘it prints S₀ and halts.’ Then, the ‘printing problem’ for the new machine is the same as the halting problem for the old machine. Since any machine that does use S₀ can first be converted to one that does not (by renaming S₀) and then altered as above, solution of the printing problem would give solution to all halting problems, and we know that this cannot be done.

11.7. Post’s Correspondence Problem

Let Σ be an alphabet having at least two elements.

Definition 11.1 Given two ordered sets of strings w1,... ,wk and x1,..., xk over Σ, is it possible to find integers i1,... ,in, 1 ≤ ij ≤ k such that wi1 ... win = xi1 ... xin? This is called Post’s Correspondence Problem (PCP). If integers i1,... ,in can be found, for an instance of a problem, that instance of PCP has a solution. If no such integers can be found, then that instance does not have a solution.

11.8. Computable Functions

In an earlier chapter, we have looked at a TM as a computing device. It computes a function. The TM M starts with input 1ⁿ. It halts in an accepting state h_a and at that time if the contents of the tape is 1^f(n), if f is defined at n. It halts at a non-accepting state or goes into a loop if f(n) is not defined at n. The partial function f is computed by M. A function which can be computed by a TM is called a Turing computable function. Here, we are restricting ourselves where the domain and range of the functions are tuples of integers. The focus on numerical function values is not as restrictive as it might sound, because any function from strings to strings can be described by encoding both arguments and values of the function as numbers.

Primitive Recursive Function

Definition 11.3 (Initial Functions) The initial functions are the following: Constant functions: For each k ≥ 0 and each a ≥ 0, the constant function : is defined by the formula: for every In the case k = 0, we may identify the function with the number a. The successor functions: is defined by the formula: s(x) = x+1 Projection functions: For each k ≥ 1 and each i with 1 ≤ i ≤ k, the projection function is defined by the formula:

Problems and Solutions

1.	Which of the following properties of RE sets are themselves RE? L contains at least two strings. L is infinite.
Solution.	This is RE. Let S = {L1, L2,... } each L in S contains at least two strings. LS = {< M > |T(M) = L and L ∊ S}. LS will be accepted by a TM MS which halts accepting < M > if < M > is in LS but may not halt if < M > is not in LS. MS takes as input < M > and uses a pair generator and simulates the behavior of M on string xi for j steps. It also keeps a counter, which initially contains 0. If M accepts xi in j steps, it increases the counter by 1. If the counter reads 2, MS halts and accepts < M >. Otherwise, it keeps on generating pair after pair and keeps testing. Since the property is nontrivial. LS is not recursive. This is not RE. Let S = {L1, L2,...} each L in S is infinite. LS = {< M > |T(M) = L and L ∊ S}. If LS is RE, it should satisfy the three conditions of Theorem 11.13. But condition 2 is violated. LS is not RE.
2.	Which of the following decision problems are decidable? Let Ti denote the ith TM. Given x, determine whether x ∊ S, where the set S is defined inductively as follows: 0 ∊ S, if u ∊ S, then u2 + 1, 3u + 2 and u! are all members of S. Given x1, x2, and x3 determine whether f(x1) = π2(x2, x3), where f is a fixed non-total recursive function (π2 is Cantor numbering).
Solution.	This is decidable. Construct a TM T halting on all inputs which stops saying ‘yes’ if x ∊ S or stops saying ‘no’ if x ∉ S. T has one input tape which initially contains x. It has six more tapes Tu, T1, T2, T3, T0, Tlist. Tu initially contains nothing (blank meaning 0) T1 initially contains 1 T2 initially contains 2 T3 initially contains 1 T1ist contains in the increasing order a list of numbers separated by #’s. Initially, it contains # 1 # 2 #. T0 is the output tape which is initially blank. When u is in Tu, T computes u2 + 1 on T1, 3u + 2 on T2 and u! on T3, it then compares x with the contents of T1, T2 and T3. If there is a match, T outputs ‘yes’ in T0 and halts. If there is no match, the contents of T1, T2, and T3 are added to the list in T1ist in the proper place. Next string from T1ist is taken and placed on Tu and the process repeats. The process stops if a match between the input and the contents of T1 or T2 or T3 is found at any time with output ‘yes.’ If the contents of T1, T2, and T3 are greater than x (input) the process stops outputting ‘no.’ This is possible as the three functions computed are monotonically increasing. Hence, the problem is decidable. This problem is undecidable. f is a non-total function and π2 is a total function. Any algorithm to solve the problem with inputs x1, x2, and x3 should have two subroutines one computing f(x1) and another computing π2(x2, x3). Since f is nontotal for some arguments, the algorithm will not come out of the subroutine for computing f(x1) and will not be able to halt. Hence, the problem is undecidable.
3.	Fermat’s last theorem, until recently one of the most-famous unproved statements in mathematics, asserts that there are no integer solution (x, y, z, n) to the equation xn + yn = zn satisfying x, y > 0 and n > 2. Show how a solution to the halting problem would allow you to determine the truth or falsity of the statement.
Solution.	Suppose the halting problem is decidable. Construct a TM T which will solve Fermat’s last theorem as follows: TM T has four tapes. In tape T1, it systematically generates ordered quadruples (x, y, z, n), x ≥ 1, y ≥ 1, z ≥ 1, n ≥ 3. Initial one is (1, 1, 1, 3). In T2, it computes xn + yn. In T3, it computes zn. It compares contexts of T2 and T3 and if they match, outputs ‘yes’ in T4. If there is no match, next quadruple is generated in T1 and the process repeats. If there is no solution for Fermat’s last theorem, T will not halt and will go on forever. Now if ‘Halt’ is the algorithm for the halting problem, give T and the first quadruple as input. If ‘Halt’ says ‘yes’, then Fermat’s last theorem has a solution. If ‘Halt’ says ‘no’, then Fermat’s last theorem has no solution.

Exercises

1.	Suppose the tape alphabets of all TMs are selected from some infinite set of symbols a1, a2,.... Explain how each TM may be encoded as a binary string.
2.	Which of the following properties of RE sets are themselves RE. L is a context-free language. L = LR
3.	Which of the following decision problems are decidable? Let Ti denote the ith TM Given i and n, determine whether Ti visits more than n squares after being started on blank tape. Given i, determine whether Ti ever writes the same symbol during two consecutive moves after being started on blank tape. Given i, determine whether there exists a TM with fewer states that computes the same one-variable function as Ti.
4.	Show that the following functions are primitive recursive. exponentiation factorial function predecessor function proper subtraction absolute difference |x – y| Sign function comparison function
5.	For each decision problem given, determine whether it is solvable or unsolvable and prove your answer. Given a TM T, does it ever reach a state other than its initial state when it starts with a blank tape? Given a TM T and a non-halting state q of T, does T ever enter state q when it begins with a blank tape? Given a TM T and a non-halting state q of T, is there an input string x that would cause T eventually to enter state q? Given a TM T, does it accept the string ∊ in an even number of moves? Given a TM T, is there a string which it accepts in an even number of moves? Given a TM T and a string w, does T loop forever on input w? Given a TM T, are there any input strings on which T loops forever? Given a TM T and a string w, does T reject input w? Given a TM T, are there any input strings rejected by T? Given a TM T, does T halt within ten moves on every string? Given a TM T, is there a string on which T halts within 10 moves? Given TMs T1 and T2, is L(T1) ⊆ L(T2) or L(T2) ⊆ L(T1)?
6.	Which of the following problems about CFGs and their languages are decidable, and which of these are not decidable? Prove. the problem of determining whether an arbitrary string belongs to the language generated by a given CFG. the problem of determining whether a CFG generates a non-empty language. the problem of determining whether the languages generated by two CFGs have any strings in common. the problem of determining whether two CFGs generate the same language. given two CFGs G1 and G2, L(G1) ⊆ L(G2). given CFG G and a regular set R determine whether L(G) = R. given CFG G and a regular set R determine whether R ⊆ L(G). given CFG G determine whether is a CFL. given two CFGs G1 and G2 determine whether L(G1) ∩ L(G2) is a CFL.