Turing

3130CIT: Theory of Computation Turing machines and undecidability (IALC, Chapters 8 and 9) Introduction to Turing’s life, Turing machines, universal machines, unsolvable problems. An undecidable problem (Section 8.1) No program H can test whether a given program will print "hello, world" as its first output on a given input. Detailed proof by self-reference leading to a contradiction. Proofs thatother problems are undecldable (or unsolvable) by reduction from a known undecidable problem. Example: Proof that the halting problem is undecidable (by reduction from the hello-world problem). Alternative proof that there exist undecidable problems (languages): Let Σ be a finite alphabet. Then Σ∗ has countably many elements. Every language over Σ is a subset of Σ∗ and is thus countable. Bydiagonalisation, the number of subsets of Σ∗ is not countable. But the number of computer programs is countable. Hence there exist undecidable problems. Turing machines (Section 8.2) A Turing machine (TM) is a finite-state machine with an infinite tape (for input and working storage) and a tape head that can read or write one tape cell and move left or right. It normally accepts the input string, orcompletes its computation, by entering a final or accepting state. Example of a TM to recognise the language { 0n 1n | n ≥ 1 } (Exx. 8.2 and 8.3, Figs. 8.9 and 8.10). Machine structure: while 0 { // ID is X*q0*Y*1* change 0 to X & move R while 0 or Y move R change 1 to Y & move L // fail if not 1 (too many 0s) while Y or 0 move L move R } while Y move R // fail if 1 (too many 1s) halt We can test thismachine on inputs 000111, 00011, 00111, 000110. Formal definition of a TM M = (Q, Σ, Γ, δ, q0 , B, F ): Q is a finite set of states, Σ is a finite input alphabet, Γ is a finite tape alphabet (Σ ⊂ Γ), δ : Q × Γ → Q × Γ × {L, R} is a transition 1

function, q0 ∈ Q is the initial state, BinΓ − Σ is the blank symbol, and F ⊆ Q is the set of final states. Instantaneous description (ID) X1 X2 . . . Xi−1 qXi. . . Xn of a TM. A move of a TM is denoted ; a sequence of zero or more moves is denoted ∗ . Turing machines to recognise languages accept by entering a final state (and halting); Turing machines to perform computation may simply halt when the computation is complete. Example of a TM to recognise palindromes (M, Ex. 16.2, Fig. 16.4). Machine structure: while true { if a { change a to B & move Rwhile a or b move R move L if B halt // odd-length palindrome if a { while a or b move L move R } } else if b { ... similarly ... } else { break } } if B halt // even-length palindrome Test on inputs abba, abbba, abaa. Example of a TM to recognise Lww = { ww | w ∈ {a, b}∗ } (M, Ex. 16.3, Fig. 16.5). Machine structure: // Stage 1: Check length is even, change as / bs to As / Bs while a or b { changea to A or b to B & move R while a or b move R move L change a to A or b to B & move L while a or b move L if A or B move R } // Stage 2: Change As and Bs in first half to as and bs if Blank halt if A or B move L while A or B change to a or b & move L if Blank move R // Stage 3: Compare first and second halves 2

while true { if a { change a to A & move R while a or b or Blank move R change Ato Blank & move L // fail if B while a or b or Blank move L if A or B move R } else if b { ... similarly ... } } if Blank halt Test on inputs aba, abaa, abab. The language L(M ) accepted by a TM M is the set of strings w in Σ∗ such that q0 w some state q in F and any tape strings α and β. αqβ for

The set of languages accepted by TMs is called the set of computably enumerable languages. The setof languages accepted by TMs that always halt is called the set of computable languages. Significance of this distinction. Example of a TM to perform integer subtraction (Ex. 8.4, Fig. 8.12). The initial tape is 0m 10n . (Who knows why they reversed the normal roles of 0s and 1s?) The TM halts with 0m−n on its tape. Machine structure: while 0 { // ID is q0ˆ(m-k)11ˆk0(n-k) change 0 to B & move R...