Crib.

$$\begin{array}{rl}\neg (\exists x\mid R:P(x))& \equiv \forall x\mid R:\neg P(x)\\ \neg (\forall x\mid R:P(x))& \equiv \exists x\mid R:\neg P(x)\end{array}$$

regular language

$$\begin{array}{rl}\hat{\delta }(q,ϵ)& =q\\ \hat{\delta }(q,xa)& =\delta (\hat{\delta }(q,x),a)\end{array}$$

All finite languages are regular, but not all regular languages are finite

Pumping Lemma

$$\text{L is regular}⟹(\exists \mid k\ge 0:(\forall x,y,z\in L\wedge |y|\ge k:(\exists u,v,w|y=uvw\wedge |v|>1:(\forall i\mid i\ge 0:xu{v}^{i}wz\in L))))$$

• demon picks $k$
• you pick $x,y,z\leftarrow xyz\in L\wedge |y|\ge k$
• demon picks $u,v,w\leftarrow uvw=y\wedge |v|\ge 1$
• you pick an $i\ge 0$, and show $xu{v}^{2}wz\notin L$

context-free grammar

$$\begin{array}{rl}\mathbb{G}=(N,\Sigma ,P,S)& N:\text{non-terminal symbols}\\ & \Sigma :\text{terminal symbols}s.t\Sigma \cap N=\varnothing \\ & P:\text{production rules}s.t\text{a finite subset of }N\times (N\cup \Sigma {)}^{\ast }\\ & S:\text{start symbol}\in N\end{array}$$

Properties

• $\exists \text{ CFG}|L(G)=L⟺L\text{ is a context-free language}$
• L is regular $⟹$ L is context-free
• $L_1,L_2\text{ are context-free}⟹L_1\cup L_2\text{ are context-free}$
• context-free languages are not closed under complement, and not closed under intersection. ($L_1\cap L_2,\sim L_1\text{ are not context-free}$)

We know that $\{a^n{b}^n{c}^n\mid n\ge 0\}$ is not CF

Pushdown Automata PDA

$$\begin{array}{rl}\text{PDA}=(Q,\Sigma ,\Gamma ,\delta ,s,\perp ,F)& Q:\text{Finite set of state}\\ & \Sigma :\text{Finite input alphabet}\\ & \Gamma :\text{Finite stack alphabet}\\ & \delta :\subset (Q\times (\Sigma \cup \{ϵ\})\times \Gamma )\times (Q\times {\Gamma }^{\ast })\\ & s:\text{start state}\in Q\\ & \perp :\text{empty stack}\in \Gamma \\ & F:\text{final state}\in Q\end{array}$$

Properties $\mathcal{L}(M)=L⟺L\text{ is context-free}$

Turing machine

$$\begin{array}{rl}\text{TM}=(Q,\Sigma ,\Gamma ,\delta ,s,q_{\text{accept}},q_{\text{reject}},\square )& Q:\text{Finite set of state}\\ & \Sigma :\text{Finite input alphabet}\\ & \Gamma :\text{Finite tape alphabet}\\ & \delta :(Q\times \Gamma )\to Q\times \Gamma \times \{L,R\}\\ & s:\text{start state}\in Q\\ & q_{\text{accept}}:\text{accept state}\in Q\\ & q_{\text{reject}}:\text{reject state}\in Q\\ & \square :\text{blank symbol}\in \Gamma \end{array}$$

Transition function: $\delta (q,x)=(p,y,D)$: when in state $p$ scan symbol $a$, write $b$ on tape cell, move the head in direction $d$ and enter state $q$

transition to $q_{\text{accept}}$ or $q_{\text{reject}}$ is a halting state and accept/reject respectively.

Properties

• A TM is “total” iff it halts on all input
• $\mathcal{L}(M)=L⟺(\forall s\mid s\in L⟺M\text{ accepts s})$
• L is recognizable: $⟺\exists \text{ TM M s.t }\mathcal{L}(M)=L$
• L is decidable: $⟺\exists \text{ total TM M s.t }\mathcal{L}(M)=L\wedge \forall s\in {\Sigma }^{\ast }\text{ M halts on s}$
• $\text{L is decidable}⟹\text{L is recognizable}$

Church-Turing Thesis

Conjecture 1: All reasonable models of computation are equivalent:

• perfect memory
• finite amount of time

Conjecture 2: Anything a modern digital computer can do, a Turing machine can do.

Equivalence model

• TMs with multiple tapes.
• NTMs.
• PDA with two stacks.

Finite Automata from Church-Turing Thesis

Finite automata can be encoded as a string:

Let $0^{n}10^{m}10^j{0}^{k_1}\dots 10^{k_n}$ be a DFA with $n$ states, $m$ input characters, $j$ final states, $k_1\dots k_n$ transitions

$$\begin{array}{rl}{A}_{\text{DFA}}& =\{M\#w\mid M\text{ is a DFA which accepts }w\}(1)\\ A_{\text{TM}}& =\{M\#w\mid M\text{ is a TM which accepts }w\}(2)\end{array}$$

M is a “recognizer” $⟹M(x)=\{\begin{array}{ll}\text{accept}& \text{if }x\in L\\ \text{reject or loop}& \text{if }x\notin L\end{array}$

M is a “decider” $⟹M(x)=\{\begin{array}{ll}\text{accept}& \text{if }x\in L\\ \text{reject}& \text{if }x\notin L\end{array}$

Decidability and Recognizability

(1) is deciable: Create a TM $M^{{}^{\prime }}$ such that $M^{{}^{\prime }}(M\#w)$ runs $M$ on $w$, therefore $M^{\prime }$ is total, or $\mathcal{L}(M)=A_{\text{DFA}}$ $M\#w\in \mathcal{L}(M^{{}^{\prime }})⟺M\text{ accepts }w⟺M\#w\in A_{\text{DFA}}$

(2) is recognizable: Create a TM $M^{{}^{\prime }}$ such that $M^{{}^{\prime }}(M\#w)$ runs $M$ on $w$ $M\#w\in \mathcal{L}(M^{{}^{\prime }})⟺M\text{ accepts }w⟺M\#w\in A_{\text{TM}}⟹\mathcal{L}(M^{{}^{\prime }})=A_{\text{TM}}$

Note that all regular language are deciable language

Proof for $A_{\text{TM}}$ is undeciable:

Assume $A_{\text{TM}}$ is decidable

$\exists$ a decider for $A_{\text{TM}}$, $D$.

Let $P$ another TM such that $P(M)$: Call $D$ on $M\#M$

Paradox machine: P never loops: $P(M)=\{\begin{array}{ll}\text{accept}& \text{if P reject M}\\ \text{reject}& \text{if P accepts M}\end{array}$

Countability

• A set $S$ is countable infinite if $\exists$ a monotonic function $f:S\to \mathbb{N}$ (isomorphism)
• A set $S$ is uncountable if there is NO injection from $S$

Theorem:

• The set of all PDAs is countably infinite
• ${\Sigma }^{\ast }$ is countably infinite (list out all string n in finite time)
• The set of all TMs is countably infinite ($\Sigma =\{0,1\}\mid \text{set of all TMs that }S\subseteq {\Sigma }^{\ast }$, so does REC, DEC, CF, REG
• The set of all languages is uncountable.

Diagonalization and Problems

The set of unrecognizable languages is uncountable. The set of all languages is uncountable.

Proof: I can encode a language with a infinite string. $\Sigma =\{0,1\}$ Consider a machine $N$ that on input $x\in \{0,1{\}}^{\ast }$ such that $L^{\ast }(i)$ is undeciable from the diagonalization. Make sure to use the negation of the dia

Theorem

• L is deciable $⟺$ L and $\sim L$ are both recognizable

Proof: $L$ is deciable $⟺\sim L$ is deciable. $L$ is deciable $⟹$ L is recognizable

Let $R_L,R_{\sim L}$ be recognizer. Create TM $M$ that runs $R_L$ and $R_{\sim L}$ on $x$ concurrently. if $R_L$ accepts $⟹$ accept, $R_{\sim L}$ accepts $⟹$ reject.

If M never halts, M decides L. If $x\in L⟹R_L(x)\text{ halts}$, and $x\notin L⟹R_{\sim L}(x)\text{ halts}$.

Reduction on universal TMs

$\sim A_{\text{TM}}=\{M\#w\mid M\text{ does not accept w}\}$. Which implies $\sim A_{\text{TM}}$ is unrecognizable

HP is undeciable, and recognizable.

$$\text{Halting problem}=\{M\#w\mid M\text{ halts on w}\}$$

Proof: Assume HP is deciable. $\exists D_{MP}(M\#w)=\{\begin{array}{ll}\text{accept}& \text{if M halts on w}\\ \text{reject}& \text{if M loops on w}\end{array}$

Build a TM $M^{{}^{\prime }}$ where $M^{{}^{\prime }}(M\#v)$:

calls $D_{MP}$ on $M\#v$:
accepts:
  - run $M$ on $v$
    - accept -> accept
    - reject -> reject
reject: reject

Therefore $M^{{}^{\prime }}$ is total. Since $M\#w\in \mathcal{L}({\mathcal{M}}^{{}^{\prime }})⟺\text{M accepts w}⟺M\#w\in A_{\text{TM}}$. Therefore $\mathcal{L}(M^{{}^{\prime }})=A_{\text{TM}}$. Which means $M^{{}^{\prime }}$ is a decider for $A_{\text{TM}}$ (which is a paradox) $\square$