Turing Machine

• A Turing machine (TM) is a 7-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{accept}},q_{\text{reject}})$, where:
  • $Q$ is a finite set of states
  • $\Gamma$ is the tape alphabet, and $\bigsqcup \in \Gamma$ is the blank symbol
  • $\Sigma \subseteq \Gamma$ is the input alphabet (where $\bigsqcup \notin \Sigma$)
  • $\delta :Q\times \Gamma ⟶Q\times \Gamma \times \{\text{L},\text{R}\}$ is the transition function
  • $q_0\in Q$ is the start state
  • $q_{\text{accept}}\in Q$ is the accept state
  • $q_{\text{reject}}\in Q$ is the reject state, where $q_{\text{reject}}\ne q_{\text{accept}}$

Configuration

• A configuration $C$ of a Turing machine $M$ is a string $uqv$, where:
  • $u,v\in {\Gamma }^{\ast }$
  • $q\in Q$ represent the current state of $M$
  • $uv$ is the contents of the tape
  • The current head is positioned over the first symbol of $v$
• A start configuration of $M$ on a string $w$ (input) is a configuration $q_{0}w$ (indicating that the machine is in the start state $q_0$ and the input $w$ is on the tape).
• (halting configuration)
  • A accepting configuration of $M$ is a configuration $u{q}_{\text{accept}}v$
  • A rejecting configuration of $M$ is a configuration $u{q}_{\text{reject}}v$
  • The halting configurations do not yield any other configurations.
• A configuration $C_1$ yields a configuration $C_2$ if the TM can go from $C_1$ to $C_2$ in one step, as the following definition for $a,b,c\in \Gamma$, $q_i,q_j\in Q$ and $u,v\in {\Gamma }^{\ast }$:
  • (Middle of tape)
    • $ua{q}_{i}bv$ yields $u{q}_{j}acv$ if $\delta (q_i,b)=(q_j,c,L)$
    • $ua{q}_{i}bv$ yields $uac{q}_{j}v$ if $\delta (q_i,b)=(q_j,c,R)$
  • (Left-hand end)
    • $q_{i}bv$ yields $q_{j}cv$ if $\delta (q_i,b)=(q_j,c,L)$
    • $q_{i}bv$ yields $c{q}_{j}v$ if $\delta (q_i,b)=(q_j,c,R)$
  • (Right-hand end)
    • $ua{q}_i$ will be handled as if it were $ua{q}_i\bigsqcup$

Acceptance

• A Turing machine $M$ accepts (or reject) a string input $w$ if there exists an accepting (or rejecting, resp.) computation history, which is a sequence of configurations $C_1,C_2,\dots ,C_k$ such that:
  • $C_1$ is the start configuration of $M$ on input $w$
  • $C_k$ is an accepting (or rejecting, respectively) configuration of $M$
  • $C_i$ yields $C_{i+1}$ for $i=1,\dots ,k-1$
• A Turing machine $M$ said to halt on input $w$ if it either accepts or rejects $w$.

Recursively Enumerable (RE)

• A language $L$ is said to be recognized by a Turing machine $M$ if:
  • For every string $w\in L$, $M$ accepts $w$
  • For every string $w\notin L$, $M$ either rejects $w$ or loops forever
• A language is said to be Turing-recognizable (or recursively enumerable (RE)) if it is recognized by some Turing machine.
• (4.18) There exists some languages that are not Turing-recognizable.
• A language is said to be co-Turing-recognizable if its complement is Turing-recognizable.
• Every infinite Turing-recognizable language has an infinite decidable subset.

Recursive (Decidable) Languages (R)

• A Turing machine $M$ is said to decide a language $L$ (and $L$ is said to be decided by $M$) if:
  • For every string $w\in L$, $M$ accepts $w$
  • For every string $w\notin L$, $M$ rejects $w$
• A Turing machine is called a decider if it halts on all inputs.
• For every language $L$, the following statements are equivalent:
  • $L$ is decidable (Turing-decidable or recursive)
  • $L$ is Turing-recognizable and co-Turing-recognizable
  • There exists a Turing machine that decides $L$
  • (p3.18) There exists an enumerator that enumerates $L$ in lexicographic order
• A language is said to be undecidable if it is not decidable.
• (Rice’s Theorem) Let $P$ be a language of TM descriptions, such that (i) $P$ is nontrivial (not empty and not all TM descriptions) and (ii) for each two TM $M_1$ and $M_2$, we have $L(M_1)=L(M_2)⟹(⟨M_1⟩\in P⟺⟨M_2⟩\in P)$. Then $P$ is undecidable.
• The set of all Turing machines is countable.
• The set of all languages is uncountable.
• The set of all strings ${\Sigma }^{\ast }$ is countable for any alphabet $\Sigma$.
• The set of all infinite binary sequences is uncountable.

Examples

Turing-unrecognizable languages

• $\overline{A_{TM}}$
• (5.30) $E{Q}_{\text{TM}}=\{M_1\text{ and }{M}_2\text{ are TMs and }L(M_1)=L(M_2)\}$
• (5.30) $\overline{E{Q}_{\text{TM}}}$
• $E{Q}_{\text{CFG}}$
• $\overline{HAL{T}_{\text{TM}}}$
• ${\text{REGULAR}}_{\text{TM}}=\{M\text{ is a TM and }L(M)\text{ is regular}\}$
• $E_{\text{TM}}$

Turing-undecidabletodo

todo check which are recognizable and which are not

• $AL{L}_{\text{CFG}}=\{G\text{ is a CFG and }L(G)={\Sigma }^{\ast }\}$
• $E_{\text{LBA}}=\{M\text{ is a LBA and }L(M)=\varnothing \}$

Turing-recognizable but not decidable languages

• $A_{TM}=\{⟨M,w⟩\mid M\text{ is a TM that accepts }w\}$
• $HAL{T}_{TM}=\{⟨M,w⟩\mid M\text{ is a TM that halts on }w\}$
• $D=\{p\mid p\text{ is an integer polynomial with an integral root}\}$
• $\overline{E{Q}_{\text{CFG}}}$

Turing-decidable languages

• $A_{\text{DFA}}$, $A_{\text{NFA}}$, $A_{\text{REX}}$
• $E_{\text{DFA}}$
• $E{Q}_{\text{DFA}}$
• $A_{\text{CFG}}$
• $E_{\text{CFG}}$
• (4.9) Every CFL is decidable.
• Every finite language is decidable.
• $D_1=\{p\mid p\text{ is an univariate integer polynomial with an integral root}\}$
• (5.9) $A_{\text{LBA}}$
• (3.12, Element distinctness problem) $E=\{\#x_1\#x_2\#\dots \#x_n\mid x_i\in \{0,1{\}}^{\ast }\text{ and }{x}_1,x_2,\dots ,x_n\text{ are all distinct}\}$

Description

• A description of a Turing machine $M$, denoted by $⟨M⟩$, is a string that encodes the transition function of $M$ in some way.

Equivalence Models

Multitape Turing Machine

• A multitape Turing machine is a Turing machine with multiple tapes, each with its own head. Each tape can be read and written to independently.
  • The transition function for a multitape Turing machine is of the form $\delta :Q\times {\Gamma }^k⟶Q\times {\Gamma }^k\times \{L,R,S{\}}^k$, where $k$ is the number of tapes.
  • $\delta (q_i,a_1,a_2,\dots ,a_k)=(q_j,b_1,b_2,\dots ,b_k,D_1,D_2,\dots ,D_k)$ means that the machine is in state $q_i$ and heads $1$ through $k$ are reading symbols $a_1,a_2,\dots ,a_k$. The machine will change to state $q_j$, write symbols $b_1,b_2,\dots ,b_k$ on the tapes, and move the heads in the directions specified by $D_1,D_2,\dots ,D_k$. (where $D_i\in \{L,R,S\}$)
• Every multitape Turing machine has an equivalent single-tape Turing machine.
• A language is Turing-recognizable iff some multitape Turing machine recognizes it.

Nondeterministic Turing Machine

• A nondeterministic Turing machine (NTM) is defined as a Turing machine but with a transition function $\delta :Q\times \Gamma ⟶\mathcal{P}(Q\times \Gamma \times \{\text{L},\text{R}\})$.
• The computation of an NTM is a tree whose branches correspond to different possibilities for the machine’s transitions. If some branch of the computation leads to the accept state, the NTM accepts its input.
• (3.16) Every NTM has an equivalent deterministic Turing machine.

Enumerator

• An enumerator $E$ is a 7-tuple $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{print}},q_{\text{halt}})$, where:
  • $Q$ is the set of states
  • $\Gamma$ is the work tape alphabet, and $\bigsqcup \in \Gamma$ is the blank symbol
  • $\Sigma$ is the output tape alphabet
  • $\delta :Q\times \Gamma ⟶Q\times \Gamma \times \{\mathrm{L},\mathrm{R}\}\times {\Sigma }_{\epsilon }$ is the transition function
  • $q_0\in Q$ is the start state
  • $q_{\text{print}}\in Q$ is the print state
  • $q_{\text{halt}}\in Q$ is the halt state (where $q_{\text{print}}\ne q_{\text{halt}}$)
• The computation of an enumerator $E$ is defined as in ordinary TM, except for the following points:
  • It has two tapes, a work tape and an output tape. both initially blank.
  • At each step,
    • If $\delta (q,a)=(r,b,D,c)$ it means that in state $q$, reading $a$, enumerator $E$:
      • enters state $r$
      • writes $b$ on the work tape
      • moves the work tape to the direction $D\in \{\mathrm{L},\mathrm{R}\}$
      • writes $c$ on the output tape, and
      • moves the output tape head to the right if $c\ne \epsilon$.
    • Whenever state $q_{\text{print}}$ is entered, the string $w$ on the output tape is said to be printed by the enumerator, the output tape is reset to blank and the head returns to the left-hand end of the output tape.
      • (note: a string may be printed more than once)
    • $E$ halts when $q_{\text{halt}}$ is entered.
  • The language enumerated by $E$ is the set $L(E)=\{w\in {\Sigma }^{\ast }\mid w\text{ is printed by }E\}$.
• (3.21) A language is Turing-recognizable iff some enumerator enumerates it.
• (p3.18) A language is Turing-decidable iff some enumerator enumerates it in lexicographic order.

Unrestricted Grammar

• An unrestricted grammar (or phrase structure grammar) is a formal grammar $G=(V,\Sigma ,R,S)$, where each production rule is of the form $\alpha \to \beta$ where:
  • $\alpha \in (V\cup \Sigma {)}^{+}$
  • $\beta \in (V\cup \Sigma {)}^{\ast }$

Reducibility

Mapping Reducibility

• A function $f:{\Sigma }^{\ast }⟶{\Sigma }^{\ast }$ is called a computable function if there exists a Turing machine $M$ such that for every string $w\in {\Sigma }^{\ast }$, $M$ halts on input $w$ and outputs $f(w)$ on its tape.
• A language $A$ is mapping reducible (or many-one reducible) to a language $B$ (denoted by $A{\le }_{\text{m}}B$), if there exists a computable function $f:{\Sigma }^{\ast }⟶{\Sigma }^{\ast }$ such that for every string $w$, we have $w\in A⟺f(w)\in B$. Such a function $f$ is called the reduction from $A$ to $B$.
• (5.22) If $A{\le }_{\text{m}}B$ and $B$ is decidable, then $A$ is decidable.
• (5.23) If $A{\le }_{\text{m}}B$ and $A$ is undecidable, then $B$ is undecidable.
• (5.28) If $A{\le }_{\text{m}}B$ and $B$ is Turing-recognizable, then $A$ is Turing-recognizable.
• (5.29) If $A{\le }_{\text{m}}B$ and $A$ is not Turing-recognizable, then $B$ is not Turing-recognizable.
• (e5.6) If $A{\le }_{\text{m}}B$ and $B{\le }_{\text{m}}C$, then $A{\le }_{\text{m}}C$.