Ch.12: An Undecidable Language

Week 12 of the book "Automata, Formal Languages, and Turing Machines" by Emre Sermutlu (2020) 12.1. Uncountable Sets and Diagonalization 12.2. Turing-Unrecognizable Languages 12.3. A_TM and HALT_TM 12.4. Reductions

64 flashcards · Computer Science · by lakesare

Part of Textbooks › Automata, Formal Languages, and Turing Machines (Emre Sermutlu) · 14 courses

[Uncountable Sets and Diagonalization] When does a set SSS have cardinality nnn ?
When there is a one-to-one correspondence between {1,2,…,n}\{1, 2, \dots, n\}{1,2,…,n} and SSS . The empty set has cardinality 0 by definition.Example: {a,b,c}\{a, b, c\}{a,b,c} has cardinality 3 via 1↔a1 \leftrightarrow a1↔a , 2↔b2 \leftrightarrow b2↔b , 3↔c3 \leftrightarrow c3↔c .
[Uncountable Sets and Diagonalization] When is a set SSS infinite?
SSS is nonempty and there is no one-to-one correspondence between SSS and {1,2,…,n}\{1, 2, \dots, n\}{1,2,…,n} for any nnn . Example: Z+={1,2,3,… }\mathbb{Z}^+ = \{1, 2, 3, \dots\}Z+={1,2,3,…} is infinite.
[Uncountable Sets and Diagonalization] When do two sets (finite or infinite) have the same cardinality?
When there is a one-to-one correspondence between them (a function that is 1-1 and onto). This is the same idea used to compare finite sets.
[Uncountable Sets and Diagonalization] When is a set countable, and when uncountable?
Countable: finite, or of the same cardinality as Z+\mathbb{Z}^+Z+ . Uncountable: not countable. For this chapter "countable" and "listable" mean the same: a 1-1 onto function f:Z+→Sf: \mathbb{Z}^+ \to Sf:Z+→S gives a list f(1),f(2),f(3),…f(1), f(2), f(3), \dotsf(1),f(2),f(3),… that contains every element of SSS .
[Uncountable Sets and Diagonalization] Why do Z+={1,2,3,… }\mathbb{Z}^+ = \{1, 2, 3, \dots\}Z+={1,2,3,…} and the even positive integers 2Z+={2,4,6,… }2\mathbb{Z}^+ = \{2, 4, 6, \dots\}2Z+={2,4,6,…} have the same cardinality?
f:Z+→2Z+f: \mathbb{Z}^+ \to 2\mathbb{Z}^+f:Z+→2Z+ , f(n)=2nf(n) = 2nf(n)=2n , is 1-1 and onto. So an infinite set can have the same cardinality as a proper subset of itself.Example: 1↔21 \leftrightarrow 21↔2 , 2↔42 \leftrightarrow 42↔4 , 3↔63 \leftrightarrow 63↔6 .
[Uncountable Sets and Diagonalization] Is the set of prime numbers P\mathbb{P}P countable?
Yes: list the primes in increasing order, 1↔21 \leftrightarrow 21↔2 , 2↔32 \leftrightarrow 32↔3 , 3↔53 \leftrightarrow 53↔5 , 4↔7,…4 \leftrightarrow 7, \dots4↔7,… The nnn -th prime has no simple explicit formula, but the correspondence exists.
[Uncountable Sets and Diagonalization] Is Z\mathbb{Z}Z countable? If so, give a 1-1 onto function f:Z+→Zf: \mathbb{Z}^+ \to \mathbb{Z}f:Z+→Z .
Yes: f(n)=n+12\boldsymbol{f(n) = \frac{n+1}{2}}f(n)=2n+1 for odd nnn , f(n)=1−n2\boldsymbol{f(n) = 1 - \frac{n}{2}}f(n)=1−2n for even nnn . Odd positive integers go to the positive integers, even ones to 0 and the negative integers. The inverse is f−1(n)=2n−1f^{-1}(n) = 2n - 1f−1(n)=2n−1 for n>0n > 0n>0 and f−1(n)=2(1−n)f^{-1}(n) = 2(1 - n)f−1(n)=2(1−n) for n≤0n \le 0n≤0 .Example: f(1),f(2),…,f(6)=1,0,2,−1,3,−2f(1), f(2), \dots, f(6) = 1, 0, 2, -1, 3, -2f(1),f(2),…,f(6)=1,0,2,−1,3,−2 .
[Uncountable Sets and Diagonalization] S1S_1S1 is countable and infinite, listed as s1,s2,s3,…s_1, s_2, s_3, \dotss1,s2,s3,… . We add nnn new elements a1,…,ana_1, \dots, a_na1,…,an . Is the result countable, and how do you list it?
Yes: list a1,…,ana_1, \dots, a_na1,…,an first, then s1,s2,…s_1, s_2, \dotss1,s2,… So k↔akk \leftrightarrow a_kk↔ak for k≤nk \le nk≤n and n+k↔skn + k \leftrightarrow s_kn+k↔sk .Example: adding 000 to Z+\mathbb{Z}^+Z+ gives the list 0,1,2,3,…0, 1, 2, 3, \dots0,1,2,3,…
[Uncountable Sets and Diagonalization] S={s1,s2,… }S = \{s_1, s_2, \dots\}S={s1,s2,…} and T={t1,t2,… }T = \{t_1, t_2, \dots\}T={t1,t2,…} are countable. Is S∪TS \cup TS∪T countable, and how do you list it?
Yes: alternate between the two lists, s1,t1,s2,t2,s3,t3,…s_1, t_1, s_2, t_2, s_3, t_3, \dotss1,t1,s2,t2,s3,t3,… An element in both sets is listed only the first time.Example: positive integers 1,2,3,…1, 2, 3, \dots1,2,3,… and negative integers −1,−2,…-1, -2, \dots−1,−2,… give 1,−1,2,−2,3,−3,…1, -1, 2, -2, 3, -3, \dots1,−1,2,−2,3,−3,…
[Uncountable Sets and Diagonalization] How does the book show that Q\mathbb{Q}Q is countable?
Put the positive rationals pq\frac{p}{q}qp in an infinite matrix (row ppp , column qqq ) and list it along the diagonals, skipping fractions already listed. Grey fractions such as 22\frac{2}{2}22 and 24\frac{2}{4}42 are skipped. The negative rationals and 0 are added the same way as for Z\mathbb{Z}Z .Example: the list starts 11,12,21,31,13,14,23,32,…\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \dots11,21,12,13,31,41,32,23,…
[Uncountable Sets and Diagonalization] Why can't you list the positive rationals pq\frac{p}{q}qp row by row in the matrix with row ppp , column qqq ?
The first row 11,12,13,…\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \dots11,21,31,… is infinite, so the list never reaches the second row. Each diagonal is finite, so listing diagonal after diagonal reaches every entry.
[Uncountable Sets and Diagonalization] What are the three steps of Cantor's diagonal argument that a set SSS is uncountable?
Assume Assume SSS is countable. List Then there is a list s1,s2,s3,…s_1, s_2, s_3, \dotss1,s2,s3,… of all elements of SSS . Diagonal Build an element of SSS that differs from sis_isi in its iii -th position, for every iii . This element is not on the list: contradiction. Example: for the infinite binary sequences, flip the iii -th digit of the iii -th sequence.
[Uncountable Sets and Diagonalization] How does Cantor's diagonal argument show that the real numbers in [0,1][0, 1][0,1] are uncountable?
Given any list a1,a2,…a_1, a_2, \dotsa1,a2,… of them, build a∈[0,1]a \in [0, 1]a∈[0,1] whose iii -th decimal digit differs from the iii -th digit of aia_iai ; then aaa is not on the list. Example: with the diagonal digits 3,7,1,93, 7, 1, 93,7,1,9 , choose a=0.5867…a = 0.5867\dotsa=0.5867… ; a≠a1a \ne a_1a=a1 (first digits differ), a≠a2a \ne a_2a=a2 (second digits differ), and so on.So R\mathbb{R}R is uncountable.
[Uncountable Sets and Diagonalization] Why is the set of all infinite binary sequences (infinite sequences of 0s and 1s) uncountable?
For any list b1,b2,…b_1, b_2, \dotsb1,b2,… , the sequence bbb whose iii -th digit is the flipped iii -th digit of bib_ibi is not on the list. Example: the diagonal digits are 0,1,1,00, 1, 1, 00,1,1,0 , so b=1,0,0,1,…b = 1, 0, 0, 1, \dotsb=1,0,0,1,… With binary notation for reals, this is the same argument as for [0,1][0, 1][0,1] .
[Uncountable Sets and Diagonalization] Is the set of all functions f:Z+→Z+f: \mathbb{Z}^+ \to \mathbb{Z}^+f:Z+→Z+ countable?
No: for any list f1,f2,…f_1, f_2, \dotsf1,f2,… , the function with f(n)≠fn(n)f(n) \ne f_n(n)f(n)=fn(n) for all nnn (e.g. f(n)=fn(n)+1f(n) = f_n(n) + 1f(n)=fn(n)+1 ) is not on the list. Each function is an infinite sequence f(1),f(2),…f(1), f(2), \dotsf(1),f(2),… , so this is the diagonal argument again.Example: if f1(1)=19f_1(1) = 19f1(1)=19 , f2(2)=7f_2(2) = 7f2(2)=7 , f3(3)=3f_3(3) = 3f3(3)=3 , f4(4)=49f_4(4) = 49f4(4)=49 , then fff starts 20,8,4,50,…20, 8, 4, 50, \dots20,8,4,50,…
[Turing-Unrecognizable Languages] Is the set of all Turing machines countable?
Yes: each TM has finitely many states, so it is encoded by a finite binary string, and the finite binary strings are countable. A TM may have several encodings, which does not matter.
[Turing-Unrecognizable Languages] How do you list all finite binary strings?
By length, and strings of the same length in numerical (lexicographic) order. Example: 0,1,00,01,10,11,000,001,010,…0, 1, 00, 01, 10, 11, 000, 001, 010, \dots0,1,00,01,10,11,000,001,010,…
[Turing-Unrecognizable Languages] Some binary strings encode no Turing machine. How does the book treat them?
As the simplest TM, which halts immediately and rejects every input; its language is ∅\varnothing∅ . Like a program with a syntax error.
[Turing-Unrecognizable Languages] Is the set of all languages over Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} countable?
No, by diagonalization. Assume a list L1,L2,…L_1, L_2, \dotsL1,L2,… ; make a matrix whose rows are the languages, whose columns are the finite strings w1,w2,…w_1, w_2, \dotsw1,w2,… , with entry 1 if wj∈Liw_j \in L_iwj∈Li and 0 otherwise. The language {wi∣wi∉Li}\{w_i \mid w_i \notin L_i\}{wi∣wi∈/Li} is not on the list.
[Turing-Unrecognizable Languages] Why must some languages be not Turing-recognizable, even before any example is known?
There are countably many Turing machines but uncountably many languages over {0,1}\{0, 1\}{0,1} . Each TM recognizes one language, so most languages are recognized by no TM.
[Turing-Unrecognizable Languages] Is every function f:Z+→Z+f: \mathbb{Z}^+ \to \mathbb{Z}^+f:Z+→Z+ computable by some computer program?
No: the programs are countable, but the functions Z+→Z+\mathbb{Z}^+ \to \mathbb{Z}^+Z+→Z+ are uncountable. "Computable" means the program gives the correct output for every input.Example: f(x)=2x+1f(x) = 2x + 1f(x)=2x+1 and f(x)=x3f(x) = x^3f(x)=x3 are computable.
[Turing-Unrecognizable Languages] What is the diagonal language LDL_{\text{D}}LD ? ( ⟨M⟩\langle M \rangle⟨M⟩ is the binary string encoding the TM MMM .)
LD={⟨M⟩∣⟨M⟩∉L(M)}\boldsymbol{L_{\text{D}} = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}}LD={⟨M⟩∣⟨M⟩∈/L(M)} : the encodings of TMs that do not accept their own encoding. "Do not accept" means reject or loop.Example: a TM that accepts exactly the binary strings of length at most 500, with an encoding of length more than 500, is in LDL_{\text{D}}LD .
[Turing-Unrecognizable Languages] A TM MMM accepts www if ∣w∣≡0(mod3)|w| \equiv 0 \pmod 3∣w∣≡0(mod3) , rejects if ∣w∣≡1(mod3)|w| \equiv 1 \pmod 3∣w∣≡1(mod3) , and loops if ∣w∣≡2(mod3)|w| \equiv 2 \pmod 3∣w∣≡2(mod3) . ⟨M⟩\langle M \rangle⟨M⟩ is the binary string encoding MMM . When is ⟨M⟩∈LD={⟨M⟩∣⟨M⟩∉L(M)}\langle M \rangle \in L_{\text{D}} = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}⟨M⟩∈LD={⟨M⟩∣⟨M⟩∈/L(M)} ?
When ∣⟨M⟩∣≡1|\langle M \rangle| \equiv 1∣⟨M⟩∣≡1 or 2(mod3)2 \pmod 32(mod3) . Then MMM rejects or loops on its own encoding, so does not accept it.
[Turing-Unrecognizable Languages] LD={⟨M⟩∣⟨M⟩∉L(M)}L_{\text{D}} = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}LD={⟨M⟩∣⟨M⟩∈/L(M)} , the encodings of TMs that do not accept their own encoding.Why is LDL_{\text{D}}LD not Turing-recognizable?
LDL_{\text{D}}LD differs from L(Mi)L(M_i)L(Mi) on the string ⟨Mi⟩\langle M_i \rangle⟨Mi⟩ , for every TM MiM_iMi . List all TMs M1,M2,…M_1, M_2, \dotsM1,M2,… and make a table: row MiM_iMi , column ⟨Mj⟩\langle M_j \rangle⟨Mj⟩ , entry "does MiM_iMi accept ⟨Mj⟩\langle M_j \rangle⟨Mj⟩ ?". The row of LDL_{\text{D}}LD is the flipped diagonal, so it is none of the rows. Example: here the row of LDL_{\text{D}}LD starts Yes, No, No.
[Turing-Unrecognizable Languages] Suppose a TM MDM_{\text{D}}MD recognizes LD={⟨M⟩∣⟨M⟩∉L(M)}L_{\text{D}} = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}LD={⟨M⟩∣⟨M⟩∈/L(M)} . What happens on input ⟨MD⟩\langle M_{\text{D}} \rangle⟨MD⟩ ?
MDM_{\text{D}}MD accepts ⟨MD⟩\langle M_{\text{D}} \rangle⟨MD⟩ if and only if it does not accept ⟨MD⟩\langle M_{\text{D}} \rangle⟨MD⟩ : a contradiction. The same kind of paradox as "This sentence is wrong."
[A_TM and HALT_TM] What is the language ATMA_{\text{TM}}ATM ?
ATM={⟨M,w⟩∣M is a TM and M accepts w}\boldsymbol{A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ accepts } w\}}ATM={⟨M,w⟩∣M is a TM and M accepts w} Deciding it means answering, after finitely many steps: "Is the given TM going to accept the given string?"
[A_TM and HALT_TM] What does the universal Turing machine (UTM) do on input ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ ?
Simulates MMM on www ; accepts if MMM enters its accept state, rejects if MMM enters its reject state. It is universal because it can simulate any TM from that TM's description.
[A_TM and HALT_TM] Does the universal Turing machine recognize or decide ATM={⟨M,w⟩∣M accepts w}A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ accepts } w\}ATM={⟨M,w⟩∣M accepts w} ?
It recognizes ATMA_{\text{TM}}ATM but does not decide it: when MMM loops on www , the simulation loops too.
[A_TM and HALT_TM] ATMA_{\text{TM}}ATM is Turing-recognizable but not Turing-decidable.
ATM={⟨M,w⟩∣M is a TM and M accepts w}A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ accepts } w\}ATM={⟨M,w⟩∣M is a TM and M accepts w}
[A_TM and HALT_TM] What is the difference between a TM MMM and ⟨M⟩\langle M \rangle⟨M⟩ ?
MMM is the machine (a set of instructions that runs); ⟨M⟩\langle M \rangle⟨M⟩ is its description as a string, usable as input. Like a program and the text file of its source code.
[A_TM and HALT_TM] ATM={⟨M,w⟩∣M accepts w}A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ accepts } w\}ATM={⟨M,w⟩∣M accepts w} Proof that ATMA_{\text{TM}}ATM is undecidable: assuming a decider HHH for ATMA_{\text{TM}}ATM , which TM DDD does the proof build?
DDD on input ⟨M⟩\langle M \rangle⟨M⟩ : run HHH on ⟨M,⟨M⟩⟩\langle M, \langle M \rangle \rangle⟨M,⟨M⟩⟩ and output the opposite (accept if HHH rejects, reject if HHH accepts). So DDD accepts ⟨M⟩\langle M \rangle⟨M⟩ exactly when MMM does not accept ⟨M⟩\langle M \rangle⟨M⟩ : DDD would decide LDL_{\text{D}}LD . DDD never loops, since HHH is a decider. (The book calls HHH TM01 and DDD TM02.)
[A_TM and HALT_TM] If HHH decides ATM={⟨M,w⟩∣M accepts w}A_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ accepts } w\}ATM={⟨M,w⟩∣M accepts w} , let DDD on input ⟨M⟩\langle M \rangle⟨M⟩ run HHH on ⟨M,⟨M⟩⟩\langle M, \langle M \rangle \rangle⟨M,⟨M⟩⟩ and output the opposite.How does running DDD on ⟨D⟩\langle D \rangle⟨D⟩ finish the proof that ATMA_{\text{TM}}ATM is undecidable?
DDD accepts ⟨D⟩\langle D \rangle⟨D⟩ if and only if DDD does not accept ⟨D⟩\langle D \rangle⟨D⟩ : contradiction, so DDD , and therefore HHH , cannot exist.
[A_TM and HALT_TM] What is Russell's paradox?
R={S∣S∉S}R = \{S \mid S \notin S\}R={S∣S∈/S} , the set of all sets that are not elements of themselves: R∈RR \in RR∈R if and only if R∉RR \notin RR∈/R . The same self-reference as in the proofs that LDL_{\text{D}}LD is not recognizable and ATMA_{\text{TM}}ATM is undecidable.
[A_TM and HALT_TM] What is the language HALTTM\text{HALT}_{\text{TM}}HALTTM (the halting problem)?
HALTTM={⟨M,w⟩∣M is a TM and M halts on input w}\boldsymbol{\text{HALT}_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w\}}HALTTM={⟨M,w⟩∣M is a TM and M halts on input w}
[A_TM and HALT_TM] How does a TM recognize HALTTM={⟨M,w⟩∣M halts on w}\text{HALT}_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ halts on } w\}HALTTM={⟨M,w⟩∣M halts on w} ?
Simulate MMM on www ; accept if MMM enters its accept state, and also accept if MMM enters its reject state. If MMM loops on www , the simulation loops too, so this is a recognizer, not a decider.
[A_TM and HALT_TM] HALTTM={⟨M,w⟩∣M halts on w}\text{HALT}_{\text{TM}} = \{\langle M, w \rangle \mid M \text{ halts on } w\}HALTTM={⟨M,w⟩∣M halts on w} How does the diagonal proof show that HALTTM\text{HALT}_{\text{TM}}HALTTM is undecidable?
From a decider HHH for HALTTM\text{HALT}_{\text{TM}}HALTTM , build DDD : on ⟨M⟩\langle M \rangle⟨M⟩ , DDD loops if HHH accepts ⟨M,⟨M⟩⟩\langle M, \langle M \rangle \rangle⟨M,⟨M⟩⟩ and halts if HHH rejects. Then DDD halts on ⟨D⟩\langle D \rangle⟨D⟩ if and only if it loops. Equivalently: fill the table "does MiM_iMi halt on ⟨Mj⟩\langle M_j \rangle⟨Mj⟩ ?" with H or L using HHH ; DDD is a row not in the table. (The book calls HHH TM03 and DDD TM04.)
[A_TM and HALT_TM] Why are decidable languages closed under complementation?
Swap the accept and reject states of a decider for LLL ; the result decides L‾\overline{L}L . This works because a decider never loops. For a recognizer, the swap fails on inputs where it loops.
[A_TM and HALT_TM] State the theorem that relates decidable and Turing-recognizable languages via complements.
LLL is decidable if and only if both LLL and L‾\overline{L}L are Turing-recognizable.
[A_TM and HALT_TM] LLL is decidable if and only if both LLL and L‾\overline{L}L are Turing-recognizable.If recognizers for LLL and L‾\overline{L}L exist, how do you decide LLL ?
Run both recognizers on www in parallel (alternating steps); accept if the one for LLL accepts, reject if the one for L‾\overline{L}L accepts. Every www is in LLL or in L‾\overline{L}L , so one of them accepts after finitely many steps.
[A_TM and HALT_TM] Are ATM‾\overline{A_{\text{TM}}}ATM and HALTTM‾\overline{\text{HALT}_{\text{TM}}}HALTTM Turing-recognizable?
No. ATMA_{\text{TM}}ATM and HALTTM\text{HALT}_{\text{TM}}HALTTM are recognizable; if their complements were too, they would be decidable (a language is decidable if and only if it and its complement are recognizable).So the Turing-recognizable languages are not closed under complementation.
[Reductions] What is the logic of a reduction proof showing problem BBB is unsolvable?
Problem AAA has no solution, and a solution for BBB would give a solution for AAA ; so BBB has no solution. Example: a decider for HALTTM\text{HALT}_{\text{TM}}HALTTM would give a decider for ATMA_{\text{TM}}ATM , so HALTTM\text{HALT}_{\text{TM}}HALTTM is undecidable.
[Reductions] MMM is a TM and www a string. What do a decider for ATMA_{\text{TM}}ATM (does MMM accept www ?) and a decider for HALTTM\text{HALT}_{\text{TM}}HALTTM (does MMM halt on www ?) output on ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ , when MMM accepts, rejects, or loops on www ?
ATMA_{\text{TM}}ATM decider: accept, reject, reject. HALTTM\text{HALT}_{\text{TM}}HALTTM decider: accept, accept, reject.
[Reductions] How do you decide ATMA_{\text{TM}}ATM (does MMM accept www ?) using a decider HHH for HALTTM\text{HALT}_{\text{TM}}HALTTM (does MMM halt on www ?)?
Run HHH on ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ ; if HHH rejects, reject. If HHH accepts, simulate MMM on www and accept or reject as MMM does. The simulation only runs when MMM halts on www , so it never loops. Since ATMA_{\text{TM}}ATM is undecidable, this is a second proof that HALTTM\text{HALT}_{\text{TM}}HALTTM is undecidable.
[Reductions] How do you decide HALTTM\text{HALT}_{\text{TM}}HALTTM (does MMM halt on www ?) using a decider AAA for ATMA_{\text{TM}}ATM (does MMM accept www ?)?
Run AAA on ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ and on ⟨M‾,w⟩\langle \overline{M}, w \rangle⟨M,w⟩ , where M‾\overline{M}M is MMM with accept and reject states swapped; accept if either accepts, otherwise reject. M‾\overline{M}M accepts www exactly when MMM rejects www , so one of the two accepts exactly when MMM halts on www .
[Reductions] Is ETM={⟨M⟩∣L(M)=∅}\text{E}_{\text{TM}} = \{\langle M \rangle \mid L(M) = \varnothing\}ETM={⟨M⟩∣L(M)=∅} decidable?
No. A decider for ETM\text{E}_{\text{TM}}ETM would give a decider for ATMA_{\text{TM}}ATM .
[Reductions] ETM={⟨M⟩∣L(M)=∅}\text{E}_{\text{TM}} = \{\langle M \rangle \mid L(M) = \varnothing\}ETM={⟨M⟩∣L(M)=∅} To reduce ATMA_{\text{TM}}ATM to ETM\text{E}_{\text{TM}}ETM , which TM M2M_2M2 is built from ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ , and how is the decider AAA for ETM\text{E}_{\text{TM}}ETM used?
M2M_2M2 on input xxx : if x=wx = wx=w , run MMM on www and accept if MMM accepts; otherwise reject. Then accept ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ if AAA rejects ⟨M2⟩\langle M_2 \rangle⟨M2⟩ , reject if AAA accepts. L(M2)={w}L(M_2) = \{w\}L(M2)={w} if MMM accepts www and L(M2)=∅L(M_2) = \varnothingL(M2)=∅ otherwise, so L(M2)≠∅ ⟺ ML(M_2) \ne \varnothing \iff ML(M2)=∅⟺M accepts www .
[Reductions] In reductions like "build M2M_2M2 from ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ , then ask the decider AAA about ⟨M2⟩\langle M_2 \rangle⟨M2⟩ ", MMM and M2M_2M2 may loop. Why does the resulting machine still never loop?
It never runs MMM or M2M_2M2 ; it only writes down ⟨M2⟩\langle M_2 \rangle⟨M2⟩ and runs AAA , which is a decider.
[Reductions] Is A111TM={⟨M⟩∣M accepts 111}\text{A111}_{\text{TM}} = \{\langle M \rangle \mid M \text{ accepts } 111\}A111TM={⟨M⟩∣M accepts 111} decidable? Which TM NNN does the reduction from ATMA_{\text{TM}}ATM build from ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ ?
No. NNN : on input 111111111 , run MMM on www and accept if MMM accepts; reject every other input. NNN accepts 111 ⟺ M111 \iff M111⟺M accepts www . So accepting ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ exactly when the decider for A111TM\text{A111}_{\text{TM}}A111TM accepts ⟨N⟩\langle N \rangle⟨N⟩ would decide ATMA_{\text{TM}}ATM .
[Reductions] How would a decider for ATMA_{\text{TM}}ATM settle Goldbach's conjecture (every even integer ≥4\ge 4≥4 is a sum of two primes)?
Write a program PPP that checks n=4,6,8,…n = 4, 6, 8, \dotsn=4,6,8,… and accepts as soon as some nnn is not a sum of two primes; ask the decider whether PPP accepts. PPP never rejects; it loops if the conjecture is true. The decider always halts, so its answer settles the conjecture without running PPP .Example: 4=2+24 = 2 + 24=2+2 , 6=3+36 = 3 + 36=3+3 , 8=3+58 = 3 + 58=3+5 , so PPP moves on past these.
[Reductions] How would a decider for ATMA_{\text{TM}}ATM or HALTTM\text{HALT}_{\text{TM}}HALTTM settle Fermat's Last Theorem (no positive integers x,y,zx, y, zx,y,z and n≥3n \ge 3n≥3 with xn+yn=znx^n + y^n = z^nxn+yn=zn )?
List all quadruples (x,y,z,n)(x, y, z, n)(x,y,z,n) (a countable set), and let a program check them one by one and halt on a solution; ask the decider whether that program halts. The program alone would never halt if there were no solution; the decider always answers. Problems this unrelated all becoming easy is a reason to expect such deciders cannot exist.
[Reductions] Place these languages in the hierarchy Regular ⊂ Context-Free ⊂ Turing-Decidable ⊂ Turing-Recognizable (or outside it): a∗a^*a∗ , anbna^nb^nanbn , anbncna^nb^nc^nanbncn , ATMA_{\text{TM}}ATM , ATM‾\overline{A_{\text{TM}}}ATM , LDL_{\text{D}}LD .
Regular a∗a^*a∗ , anbma^nb^manbm Context-free, not regular anbna^nb^nanbn , palindromes Decidable, not context-free anbncna^nb^nc^nanbncn Recognizable, not decidable ATMA_{\text{TM}}ATM , HALTTM\text{HALT}_{\text{TM}}HALTTM Not Turing-recognizable ATM‾\overline{A_{\text{TM}}}ATM , HALTTM‾\overline{\text{HALT}_{\text{TM}}}HALTTM , LDL_{\text{D}}LD
[Reductions] Where are the finite languages in the hierarchy Regular ⊂ Context-Free ⊂ Turing-Decidable ⊂ Turing-Recognizable?
In the regular languages. A finite language {w1,…,wk}\{w_1, \dots, w_k\}{w1,…,wk} is given by the regular expression w1∪⋯∪wkw_1 \cup \dots \cup w_kw1∪⋯∪wk .Example: {a,ab,b}=L(a∪ab∪b)\{a, ab, b\} = L(a \cup ab \cup b){a,ab,b}=L(a∪ab∪b) .
[Exercises] Is the set of all polynomials with integer coefficients countable?
Countable. For each NNN , only finitely many polynomials a0+a1x+⋯+adxda_0 + a_1x + \dots + a_dx^da0+a1x+⋯+adxd have d+∣a0∣+⋯+∣ad∣=Nd + |a_0| + \dots + |a_d| = Nd+∣a0∣+⋯+∣ad∣=N ; list them for N=0,1,2,…N = 0, 1, 2, \dotsN=0,1,2,… Example: N=1N = 1N=1 gives 1,−11, -11,−1 ; N=2N = 2N=2 gives 2,−2,x,−x2, -2, x, -x2,−2,x,−x .
[Exercises] Is the set of all infinite strings over Σ={0,1,2}\Sigma = \{0, 1, 2\}Σ={0,1,2} countable? Use Cantor's argument if not.
Uncountable. For any list s1,s2,…s_1, s_2, \dotss1,s2,… , take the string whose iii -th symbol is (the iii -th symbol of sis_isi ) +1 mod 3+ 1 \bmod 3+1mod3 ; it is not on the list.Example: diagonal symbols 2,0,12, 0, 12,0,1 give 0,1,2,…0, 1, 2, \dots0,1,2,…
[Exercises] Over Σ={a,b,c,d,e}\Sigma = \{a, b, c, d, e\}Σ={a,b,c,d,e} : is the set of all finite words countable? The set of all infinite strings?
Finite words: countable. Infinite strings: uncountable. Finite words are listed by length, then alphabetically ( 5n5^n5n words of length nnn ). Infinite strings: change the iii -th letter of the iii -th string.Example: the list of finite words starts ε,a,b,c,d,e,aa,ab,…\varepsilon, a, b, c, d, e, aa, ab, \dotsε,a,b,c,d,e,aa,ab,…
[Exercises] Is the set of all 2×22 \times 22×2 matrices with entries from Q\mathbb{Q}Q countable? With entries from R\mathbb{R}R ?
From Q\mathbb{Q}Q : countable. From R\mathbb{R}R : uncountable. A rational matrix is a quadruple of rationals, and finite products of countable sets are countable. The real matrices (x000)\begin{pmatrix} x & 0 \\ 0 & 0 \end{pmatrix}(x000) alone correspond one-to-one to R\mathbb{R}R .
[Exercises] Is a countable union S1∪S2∪…S_1 \cup S_2 \cup \dotsS1∪S2∪… of countable sets countable?
Yes. Put the jjj -th element of SiS_iSi in row iii , column jjj of an infinite matrix and list it along the diagonals, skipping repeats, as for Q\mathbb{Q}Q .
[Exercises] Is the set of all subsets of a countably infinite set countable?
No. For Z+\mathbb{Z}^+Z+ : given a list S1,S2,…S_1, S_2, \dotsS1,S2,… of subsets, D={i∣i∉Si}D = \{i \mid i \notin S_i\}D={i∣i∈/Si} differs from each SiS_iSi at iii . (For a finite set the set of subsets is finite, hence countable.)Example: if S1={1}S_1 = \{1\}S1={1} , S2={1,3}S_2 = \{1, 3\}S2={1,3} , S3={3}S_3 = \{3\}S3={3} , then 1∉D1 \notin D1∈/D , 2∈D2 \in D2∈D , 3∉D3 \notin D3∈/D .
[Exercises] Is the set of all solutions of second degree equations ax2+bx+c=0ax^2 + bx + c = 0ax2+bx+c=0 with integer coefficients countable?
Yes. The triples (a,b,c)∈Z3(a, b, c) \in \mathbb{Z}^3(a,b,c)∈Z3 are countable, and each equation has at most 2 solutions.Example: x2−x−1=0x^2 - x - 1 = 0x2−x−1=0 gives 1+52\frac{1 + \sqrt{5}}{2}21+5 and 1−52\frac{1 - \sqrt{5}}{2}21−5 .
[Exercises] ETM={⟨M⟩∣L(M)=∅}\text{E}_{\text{TM}} = \{\langle M \rangle \mid L(M) = \varnothing\}ETM={⟨M⟩∣L(M)=∅} is undecidable.Is EQTM={⟨M,N⟩∣L(M)=L(N)}\text{EQ}_{\text{TM}} = \{\langle M, N \rangle \mid L(M) = L(N)\}EQTM={⟨M,N⟩∣L(M)=L(N)} decidable?
Not decidable. Let N∅N_\varnothingN∅ reject every input. Then ⟨M⟩∈ETM ⟺ ⟨M,N∅⟩∈EQTM\langle M \rangle \in \text{E}_{\text{TM}} \iff \langle M, N_\varnothing \rangle \in EQ_{\text{TM}}⟨M⟩∈ETM⟺⟨M,N∅⟩∈EQTM , so a decider for EQTM\text{EQ}_{\text{TM}}EQTM would decide ETM\text{E}_{\text{TM}}ETM .
[Exercises] Is REGTM={⟨M⟩∣L(M) is regular}\text{REG}_{\text{TM}} = \{\langle M \rangle \mid L(M) \text{ is regular}\}REGTM={⟨M⟩∣L(M) is regular} decidable?
Not decidable. From ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ build M2M_2M2 : on input xxx , accept if x=0n1nx = 0^n1^nx=0n1n ; otherwise run MMM on www and accept if MMM accepts. L(M2)=Σ∗L(M_2) = \Sigma^*L(M2)=Σ∗ (regular) if MMM accepts www , and {0n1n}\{0^n1^n\}{0n1n} (not regular) otherwise. So a decider for REGTM\text{REG}_{\text{TM}}REGTM would decide ATMA_{\text{TM}}ATM .
[Exercises] Is FINTM={⟨M⟩∣L(M) contains finitely many strings}\text{FIN}_{\text{TM}} = \{\langle M \rangle \mid L(M) \text{ contains finitely many strings}\}FINTM={⟨M⟩∣L(M) contains finitely many strings} decidable?
Not decidable. From ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ build M2M_2M2 : on any input, run MMM on www and accept if MMM accepts. L(M2)=Σ∗L(M_2) = \Sigma^*L(M2)=Σ∗ if MMM accepts www , and ∅\varnothing∅ otherwise; so MMM accepts w ⟺ ⟨M2⟩∉FINTMw \iff \langle M_2 \rangle \notin FIN_{\text{TM}}w⟺⟨M2⟩∈/FINTM .
[Exercises] Is EVENTM={⟨M⟩∣L(M) contains an even number of strings}\text{EVEN}_{\text{TM}} = \{\langle M \rangle \mid L(M) \text{ contains an even number of strings}\}EVENTM={⟨M⟩∣L(M) contains an even number of strings} decidable?
Not decidable. From ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ build M2M_2M2 : accept input 000 ; on input 111 , run MMM on www and accept if MMM accepts; reject all other inputs. L(M2)={0,1}L(M_2) = \{0, 1\}L(M2)={0,1} (2 strings) if MMM accepts www , and {0}\{0\}{0} (1 string) otherwise.
[Exercises] Is ONETM={⟨M⟩∣L(M) contains exactly one string}\text{ONE}_{\text{TM}} = \{\langle M \rangle \mid L(M) \text{ contains exactly one string}\}ONETM={⟨M⟩∣L(M) contains exactly one string} decidable?
Not decidable. From ⟨M,w⟩\langle M, w \rangle⟨M,w⟩ build M2M_2M2 : on input 000 , run MMM on www and accept if MMM accepts; reject all other inputs. L(M2)={0}L(M_2) = \{0\}L(M2)={0} if MMM accepts www , and ∅\varnothing∅ otherwise.