计算理论笔记（四）Undecidability Enumerator

Halting Problem

• H = { H=\{ H={“$M$”“$w$”: $M$ is a TM that halts on $w\}$
• $H$ is R.E.
• If $H$ is recursive, then all R.E. languages are recursive
• $H$ is not recursive

Lemma: $H$ is recursively enumerable

• Universal TM: $U=$ on input “$M$”“$w$”
  1. run $M$ on “$w$”
  2. if $M$ halts on “$w$”, halts on “$M$”“$w$”
• $U$ halts on “$M$”“$w$” $⟺$ $M$ halts on $w⟺$ “$M$”“$w$”$\in H$
• $U$ semidecides $H$

Lemma: If $H$ is recursive, so are all R.E. languages

• Also: $H$ is complete for the class of R.E. languages
• Let $A$ be a R.E. language and $M$ be a TM that semidecides $A$
• Is $w\in A$? $⟺$ Does $M$ halt on $w$? $⟺$ “$M$”“$w$”$\in H$
• If $H$ is recursive, there exists a TM M H M_H MH​ that decides $H$
• M A = M_\mathrm{A}= MA​= on input $w$
  1. run M H M_\mathrm{H} MH​ on “$M$”“$w$”
  2. if M H M_\mathrm{H} MH​ accepts “$M$”“$w$”, accept $w$
  3. else reject

Theorem: $H$ is not recursive

• H = { H=\{ H={“$M$”“$w$”: $M$ is a TM that halts on $w\}$
• H ′ = { H'=\{ H′={“$M$”: $M$ is a TM that halts on “$M$”$\}$
• H d = { H_d=\{ Hd​={“$M$”: $M$ is a TM that does not halt on “$M$”$\}$
• Claim: If $H$ is recursive, then H d H_d Hd​ is also recursive
  • If $H$ is recursive, there exists a TM M H M_H MH​ that decides $H$
  • M d = M_\mathrm{d}= Md​= on input “$M$”
    1. run M H M_\mathrm{H} MH​ on “$M$”““$M$””
    2. if M H M_\mathrm{H} MH​ accepts “$M$”““$M$””, reject “$M$”
    3. else accept
• Claim: H d H_d Hd​ is not R.E.
  • Suppose H d H_d Hd​ is R.E., there exists a TM $D$ semidecides H d H_d Hd​
  • $D$ on input “$M$”
    • halts if “$M$” ∈ H d \in H_d ∈Hd​, therefore $M$ does not halt on “$M$”
    • does not halt if “$M$” ∉ H d \notin H_d ∈/​Hd​, therefore $M$ halts on “$M$”
  • Barber Dilemma: $D$ on input “$D$”
    • halts if $D$ does not halt on “$D$”
    • does not halt if $D$ halts on “$D$”

Lemma: $L$ is recursive iff $L$ and L ‾ \overline{L} L is both R.E.

• sufficiency: recursive under complement
  • $L$ and L ‾ \overline{L} L are both recursive, therefore also R.E.
• necessity: M L M_L ML​ and M L ‾ M_{\overline{L}} ML​ semidecides $L$ and L ‾ \overline{L} L, respectively
  • M ∗ = M^*= M∗= on input $w$
    1. run M L M_\mathrm{L} ML​ and M L ‾ M_\mathrm{\overline{L}} ML​ on $w$ in parallel
    2. if M L M_\mathrm{L} ML​ halts, accept $w$
    3. else if M L ‾ M_\mathrm{\overline{L}} ML​ halts, reject $w$

Theorem: The class of R.E. languages is not closed under complement

• $H$ and H ‾ \overline{H} H are both R.E., then $H$ is recursive

Definition

• Let $A$ and $B$ be two languages over Σ A \Sigma_A ΣA​ and Σ B \Sigma_B ΣB​, respectively
• $A$ reduction from $A$ to $B$ is a computable function f : Σ A ∗ → Σ B ∗ f:\Sigma_A^*\to\Sigma_B^* f:ΣA∗​→ΣB∗​

Theorem

• Suppose that there is a reduction $f$ from $A$ to $B$, if $B$ is recursive, so is $A$
• M A = M_\mathrm{A}= MA​= on input $w$
  1. compute $f(w)$
  2. run M B M_\mathrm{B} MB​ on $f(w)$
  3. if M B M_\mathrm{B} MB​ accepts $f(w)$, accept $w$
  4. else reject
• $A⪯B$

Theorem: The following problems are undecidable

• A = { A=\{ A={“$M$”: $M$ is a TM that halts on $e\}$
  • Given a TM $M$ and a string $w$
  • M w = M_w= Mw​= on input $w$
    1. run $M$ on $u$
    2. if $M$ halts on $u$, halts
  • M w M_w Mw​ halts on $e$ (“ M w M_w Mw​”$\in A$) $⟺$ M w M_w Mw​ halts on every input ⟺ M w \iff M_w ⟺Mw​ halts on $w$ (“$M$”“$w$”$\in H$)
  • Notice: “ M w M_w Mw​” is used as input of $A$
  • $H⪯A$
• B = { B=\{ B={“$M$”: $M$ is a TM that halts on some strings$\}$
  • $f($“$M$”“$w$”$)=$“ M w M_w Mw​”
  • $H⪯B$
• C = { C=\{ C={“$M$”: $M$ is a TM that halts on every string$\}$
  • $f($“$M$”“$w$”$)=$“ M w M_w Mw​”
  • $H⪯C$
• D = { D=\{ D={" M 1 M_1 M1​"“ M 2 M_2 M2​”: M 1 M_1 M1​ and M 2 M_2 M2​ are two TMs that halts on the same string$\}$
  • Let M ∗ M^* M∗ be a TM with S ∈ H ⟺ M ∗ S\in H\iff M^* S∈H⟺M∗ halts on every input
  • $f($“$M$”$)=$“$M$”“ M ∗ M^* M∗”
  • $C⪯D$
• E 1 = { E_1=\{ E1​={“$M$”: $M$ is a TM that $L(M)$ is regular$\}$
• E 2 = { E_2=\{ E2​={“$M$”: $M$ is a TM that $L(M)$ is context-free$\}$
• E 3 = { E_3=\{ E3​={“$M$”: $M$ is a TM that $L(M)$ is recursive$\}$
  • Given a TM $M$ and a string $w$
  • $f($“$M$”“$w$”$)=$“ M w M_w Mw​”
  • M w = M_w= Mw​= on input $v$
    1. run $M$ on $w$
    2. run $U$ on “$M$”“$v$”
  • if “$M$”“$w$”$\notin H$, does not halt in step 1, L ( M w ) = ∅ L(M_w)=\varnothing L(Mw​)=∅
  • if “$M$”“$w$”$\in H$, L ( M w ) = L ( U ) = H L(M_w)=L(U)=H L(Mw​)=L(U)=H
  • L ( M w ) L(M_w) L(Mw​) is regular/context-free/recursive iff “$M$”“$w$”$\notin H$
  • H ⪯ E 1 ‾ , E 2 ‾ , E 3 ‾ H\preceq \overline{E_1},\overline{E_2},\overline{E_3} H⪯E1​​,E2​​,E3​​
• There is a certain fixed TM $M$, for which the following problem is undecidable:
  • Given a string $w$, does $M$ halt on $w$?
  • Language: $L(M)$
  • Run $U$ on “$M$”“$w$”

Rice’s Theorem

• Suppose $\mathcal{L}$ is a proper, non-empty subset of all R.E. languages, the following is undecidable: given a TM $M$, is $L(M)\in \mathcal{L}$?
• S = { S=\{ S={“$M$”: $M$ is a TM that $L(M)\in \mathcal{L}\}$
• Proof:
  • Assume $\varnothing \notin \mathcal{L}$, otherwise let $\mathcal{L}$ be its complement
  • Let a language $A\in \mathcal{L}$ and a TM M A M_\mathrm{A} MA​ that semidecides $A$
  • $f($“$M$”“$w$”$)=$ on input $u$
    1. run $M$ on $w$
    2. run M A M_\mathrm{A} MA​ on $u$
  • if “$M$”“$w$”$\notin H$, $L(f($“$M$”“$w$”$))=\varnothing$
  • if “$M$”“$w$”$\in H$, $L(f($“$M$”“$w$” ) ) = L ( M A ) = A ∈ L ))=L(M_A)=A\in\mathcal{L} ))=L(MA​)=A∈L
  • $H⪯S$
• Given a TM $M$, does $M$ halt on $e$?
  • L = { L \mathcal{L}=\{L L={L: $L$ is R.E. and $e\in L\}$
• Given a TM $M$, does $M$ halt on some input?
  • L = { L \mathcal{L}=\{L L={L: $L$ is R.E. and $L\ne \varnothing \}$
• Given a TM $M$, does $M$ halt on every input?
  • L = { Σ ∗ } \mathcal{L}=\{\Sigma^*\} L={Σ∗}
• Given a TM $M$, is $L(M)$ regular/context-free/recursive?
  • L = { L \mathcal{L}=\{L L={L: $L$ is regular/context-free/recursive$\}$

Theorem: A language $L$ is R.E. iff it is Turing enumerable

• Assume $L$ is infinite
• sufficiency:
  • Let $M$ be a TM that enumerates $L$
  • Construct a TM M ′ M' M′ to semidecide $L$
  • M ′ = M'= M′= on input $w$
    1. run $M$ to enumerate $L$
    2. every time $M$ outputs a string, compare it with $w$, and halt if they match
• necessity:
  • Let $M$ be a TM that semidecides $L$
  • Construct a TM M ′ M' M′ to enumerate $L$
  • Name all strings over $\Sigma$ as s 1 , s 2 , … s_1,s_2,\dots s1​,s2​,… in lexicographical order
  • M ′ = M'= M′= on input $w$
    1. for $i=1,2,\dots$
    • run $M$ on s 1 , s 2 , … , s i s_1,s_2,\dots,s_i s1​,s2​,…,si​ at most $i$ steps
    2. if $M$ hatls on s j s_j sj​ in $i$ steps, output s j s_j sj​

Definition

• Let $M$ be a TM enumerates $L$, we say $M$ lexicographically enumerate $L$ if whenever ( q , ⊳ ⊔ ‾ w ) ⊢ M + ( q , ⊳ ⊔ ‾ w ′ ) (q,\rhd\underline{\sqcup}w)\vdash^+_M(q,\rhd\underline{\sqcup}w') (q,⊳⊔​w)⊢M+​(q,⊳⊔​w′)
  • w ′ w' w′ is after $w$ in lexico order

Theorem: A language is recursive iff it is lexico Turing enumerable

• sufficiency:
  • Let $M$ be a TM that decides $L$
  • Construct a TM M ′ M' M′ to lexico enumerate $L$
  • M ′ = M'= M′= on input $w$
    1. generate all strings voer $\Sigma$ in lexico order
    2. run $M$ on each string $w$ to see if $w\in L$
    3. if $M$ accepts $w$, accept
    4. else reject
• necessity:
  • Let $M$ be a TM that lexico enumerates $L$
  • Construct a TM M ′ M' M′ to decide $L$
  • M ′ = M'= M′= on input $w$
    1. run $M$ to enumerate $L$ until $M$ outputs a string is after $w$ in lexico order
    2. if $w$ is among strings that output, accept $w$
    3. else reject

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！