cs2200

Types of grammar:

1. Right linear
2. Context free
3. unrestricted

Types of machine models:

1. finite memory: finite automata, regex
2. finite memory with stack: pushdown automata
3. unrestricted: turing machines, post systems, λ calculus etc.

There is a one to one correspondence for the numberings above.

Gödel’s incompleteness theorem: No matter how strong a deductive system is, there are always statements that are true but unprovable.

Strings and Sets

Decision problem is a function that has a one bit output: true or false, 1 or 0.

To completely specify a decision problem, specify a set of possible inputs, and the subset for which the output is true.

Encoding the input of a decision problem as a fixed finite length string is possible over some fixed finite alphabet.

A finite alphabet is any finite set. A finite length string is a sequence of the elements.

Set ops for two sets:

• Union
• Intersection
• Complement over set of all strings: Basically, it depends on the set of all strings that is chosen and hence this is often written as $\Sigma^* — A$ to emphasize this.
• Concatenation of two sets: $AB = {xy | x \in A; y \in B}$.

Set ops on one set:

• asterate A^* of a set. $A^* = \bigcup_{n\geq 0}A^n$
• A⁺ of a set. $A^+ = \bigcup_{n \geq 1}A^n$.

States and transitions

A state of a system gives all the relevant information of a system, like a snapshot. Transitions are changes of states.

If both are finite, then the system is called a finite state transition system. We model them using finite automata.

Deterministic Finite Automata

Formally,

$$M = \left(Q,\Sigma,\delta,s,F\right)$$

• Q is the finite set of states.
• $\Sigma$ is the finite set of the input alphabet.
• $\delta$ is the transition function that takes the current state and the input character as the inputs and gives the next state as the output.
• s is the start state.
• F is the finite subset of Q that are acceptable as the final states.

To extend the character input to a string, we define $\hat{\delta}$ inductively as follows:

• $\hat{\delta}\left(q, xa\right) = \delta\left(\hat{\delta}\left(q, x\right), a\right)$
• $\hat{\delta}\left(q, \epsilon\right) = q$

Where $x$ is a string, $a$ is a character, and $\epsilon$ is the empty input.

These can also be translated to the finite state machines discussed here.

A string $x$ is accepted by an automation $M$ if

$$\hat{\delta}\left(s,x\right) \in F$$

A set or a language accepted by $M$ is the set of all strings accepted by some automata $M$, also called $L(M)$. Any subset of $\Sigma^*$ is said to be regular if it is accepted by some automaton $M$.

Any finite subset of $\Sigma^*$ is regular (brute-force all strings).

Proof that union of two regular languages is regular:

Let DFA 1 be $\left(Q_1, \Sigma, \delta_1, s_1, F_1\right)$ and DFA 2 be $\left(Q_2, \Sigma, \delta_2, s_2, F_2\right)$

The final automata has the cartesian product of the two sets of states as the set of states (Q), and the delta is also from $Q_1 \times Q2$ to $Q_1 \times Q2$ . The set of final states is $Q_1\times F_2 \cup Q_2 \times F_1$. Also, $\hat{\delta}\left(\left(s_1, s_2\right), w\right) = \left(\hat{\delta}\left(s_1, w\right),\hat{\delta}\left(s_2, w\right)\right)$

Proof the the complement of a regular language is also regular:

All accepted final states become non-accepted, while all non-accepted final states become accepted.

Proof that the intersection of two regular languages is also regular:

Using set properties (De Morgan’s Law), or instead follow the proof of union and replace the final set with $F_1 \times F_2$.

Non-deterministic Finite Automata

A finite automata where the next state is not necessarily determined by the current state, and the input symbol. It is effectively in a state of guessing.

To show that an automata accepts a set $B$, we argue that there exists a lucky sequence of guesses that lead from the start state to an accept state when the end of $x\in B$ is reached, but for any string outside the set, it is impossible.

Formally,

$$M = \left(Q,\Sigma,\Delta,S,F\right)$$

• Q is the finite set of states.
• $\Sigma$ is the finite set of the input alphabet.
• $\Delta$ is the transition function that takes the current state and the input character as the inputs and gives the next state as the output. In this case, there are $2^Q$ possible outputs, instead of the $Q$ possible outputs in case of DFA. Each output corresponds to a unique element in the power set of $Q$.
• S is the subset of acceptable states called the start states.
• F is the finite subset of Q that are acceptable as the final states.

To define the acceptance, we use the following rules:

$$\hat{\Delta}\left(A,\epsilon\right) = A$$

$$\hat{\Delta}\left(A, xa\right) = \bigcup_{q\in \hat{\Delta}\left(A,x\right)} \Delta\left(q,a\right)$$

Instead of the usual one state, we have the input to be a subset of the possible state for $\hat{\Delta}$.

Acceptance happens when $x \in \Sigma^*$ satisfies $\hat{\Delta} \left(S,x\right) \cap F \neq \phi$

Proof for Deterministic and Non-deterministic Finite Automata being equivalent:

• First we prove that $\hat{\Delta}\left(A, xy\right) = \hat{\Delta}\left(\hat{\Delta}\left(A, x\right), y\right)$

Induction on |y|:

For |y| = 0, it is trivially true from the above equations.

Assume for |y| ≤ n,

$$\begin{align*} \hat{\Delta}\left(A, xya\right) &= \bigcup_{q\in \hat{\Delta}\left(A,xy\right)} \Delta\left(q,a\right) \ & = \bigcup_{q\in \hat{\Delta}\left(\hat{\Delta}\left(A,x\right),y\right)} \Delta\left(q,a\right) \ & = \hat{\Delta}\left(\hat{\Delta}\left(A,x\right),ya\right) \end{align*}$$

• Second, the function $\hat{\Delta}$ commutes with the set union, i.e., $\hat{\Delta}(\bigcup_i A_i,x) = \bigcup_i \hat{\Delta}(A_i, x)$

Induction on |x|:

For |x| = 0, it is trivially true.

Assume for |x| ≤ n.

$$\begin{align*} \hat{\Delta}\left(\bigcup_i A_i, xa\right) & = \hat{\Delta}\left(\hat{\Delta}\left(\bigcup_i A_i,x\right),a\right) \ & = \hat{\Delta}\left(\bigcup_i\hat{\Delta}\left(A_i, x\right),a\right) \ & = \bigcup_i \hat{\Delta}\left(\hat{\Delta}\left(A_i , x\right), a\right) \ & = \bigcup_i\hat{\Delta}\left(A_i, xa\right) \end{align*}$$

Now the following two automata can be shown to accept the same set.

$$\left(Q, \Sigma, \Delta, S, F\right) = \left(2^Q, \Sigma, \hat{\Delta}, S, { A | A \subseteq Q, A \cap F ≠ \phi} \right)$$

To create a minimal DFA from an NFA, check the decision tree for the NFA and do a BFS, stopping when you don’t get any new states.

$\epsilon$ transition

This has an $\epsilon$ slip that allows the state to transition without reading any input symbol.

Proof that $\epsilon$ transition NFA’s have an equivalent NFA with just one start state and no $\epsilon$ transitions.

Defn: $\epsilon$ closure: The set of all states that a state can reach on an $\epsilon$ transition.

Define a new transition function such that the states attained by the state with $\epsilon$ transitions further take one symbol.

For an $\epsilon$ NFA to be converted to a regular NFA, we define

$$\begin{align*} \Delta'\left(q,\sigma\right) = \bigcup_{q'\in \epsilon(q)} \Delta\left(q', \sigma\right) \end{align*}$$

where $\epsilon(q)$ is the $\epsilon$ closure of q.

The final states

$$F' = {q | \epsilon(q)\cap F \neq \phi}$$

Everything else remains the same.

Pattern Matching

• $a$ for each $a \in \Sigma$, matched by $a$ only.
• $\epsilon$, matched by the empty string.
• $\phi$, matched by nothing.
• #, matched by any symbol in $\Sigma$.
• $@$, matched by anything in $\Sigma^*$.

Combining patterns

• $x$ matches $\alpha + \beta$ if $x$ matches either of those.
• $x$ matches $\alpha\cap\beta$ if $x$ matches both of them.
• $x$ matches $\alpha\beta$ if $x$ matches $\alpha$ followed by $\beta$.
• $x$ matches $~\alpha$ if it doesn’t match $\alpha$.
• $x$ matches $\alpha^*$ and $\alpha^+$ the same way as regex.

NOTE:
$\left(0 + 1\right)^*$ accepts 010101
$0^* + 1^*$ accepts 000000 or 111111 but only strings of one symbol

For any pattern $R$, we define $L(R)$ to be the language that matches the pattern $R$.

Any regular language can have countably infinite representations in form of patterns.

Theorem: If $R$ is a regular expression, then $L(R)$ is regular.

Proof: Check for each possible case and all of them can be decomposed into a combination of the above situations.

It is always possible to remove the complement in a regular expression.

DFAs to Regex

• State elimination
  • Keep remaining states
  • Replace transitions with transitions labelled as regex.
  • while true

Class

Theorem: Set of all C Programs is countable.

Proof:

Represent the ascii source code in binary. Then it will be a subset of ${0,1}^*$ and that is bijective with the natural numbers ($n(b) + 2^{|b|} -1$). It is also obviously infinite.

Hilbert’s Entscheidungs Problem: Given a mathematical statement, is it derivable from the axioms?

Defn: A language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$.

Theorem: The cardinality of all the languages over some alphabet is uncountably infinite, i.e., $\left|\mathcal{P}\left(L\right)\right| > \left|\mathbb{N}\right|$.

Proof:

Cantor’s argument:

Set of all languages = $\mathcal{P}\left({0,1}^*\right)$

The entries in the table tell whether that particular element is present in the subset is gotten from the result or not.

Take the diagonal and bit flip all bits. It will differ from all the strings in the table by atleast one bit.

Go to top till Deterministic Finite Automata along with a few examples of languages based on the problem.

Limits of DFAs

• DFAs have finite memory.
• They can also only read one symbol at a time from left to right.

For instance, there is no way of constructing a DFA that can accept $L = {0^n1^n | n \in \mathbb{N}}$.

Similarly, there is no DFA that can accept the language $L = {0^{2^n}| n \in \mathbb{N}}$

Important Proof

If $L$ is regular, where $L = {ww | w \in \Sigma^* }$, then $\sqrt{L}$ is also regular.

Proof:

Let the DFA be $\left(Q, \Sigma, \delta, q_0, F\right)$. We define the NFA as follows:

$$N = \left(Q \times Q \times Q, \Sigma, \Delta, A, f\right)$$

where

$$\begin{align} A &= \bigcup_{i\in Q} {\left(i, q_0, i\right)} \ f &= \bigcup_{i \in Q\atop z\in F} {\left(i, i, z\right)} \ \Delta\left(\left(i, \alpha, \beta\right), a_0\right) &= \left(i, \delta\left(\alpha, a_0\right), \delta\left(\beta, a_0\right)\right) \end{align}$$

Pumping Lemma

Let $L$ be a regular language. $\exists k > 0$, s.t. $\forall x,y,z$ s.t. $xyz \in L$ and $|y| > k$, $\exists u,v,w$ s.t. $y = uvw, v\ne \epsilon$ s.t. $\forall i \geq 0, xuv^iwz \in L$.

Proof: $\exists M = \left(Q, \Sigma, \delta, q_0, F\right)$ s.t. $L\left(M\right) = L$.

Set $k = |Q|$

Let $x,y,z \in \Sigma^*$ s.t. $|y| > k$ & $xyz \in L$

$$\begin{align*} \hat{\delta}\left(q_0, x\right) &= q & \hat{\delta}\left(q, y\right) &= q' & \hat{\delta}\left(q', z\right) & \in F & \end{align*}$$

$y = y_1y_2…y_r, r> k$. We define $q_i = \hat{\delta} \left(q, y_1y_2…y_i\right)$

Consider the sequence $q_1q_2q_3…q_r$

$\implies \exists s, t$ s.t. $q_s = q_t$ in the sequence (by PHP).

Define

$$u = y_1y_2…y_s$$

$$v = y_{s+1}y_{s+2}…y_t$$

$$w = y_{t+1}y_{t+2}…y_r$$

$$\begin{align} \hat{\delta}\left(q_0, x\right) &= q \ \hat{\delta}\left(q, u\right) &= q_s \ \hat{\delta}\left(q_s, v\right) &= q_s \implies \hat{\delta} \left(q_s, v^i\right) = q_s \ \hat{\delta}\left(q_s, wz\right) &\in F \end{align}$$

An analogy with a 2 player game:

Prover: I’ll give you a number k

Spoiler: I’ll find x, y, z such that the concatenation is in the language with length of y > k

Prover: I’ll split y into u, v, w where v is non-empty.

Spoiler: I’ll find an i > 0 such that the pumping lemma string doesn’t belong in the DFA. If I do that, I’ll win. And L will not be regular.

An alternate way to prove that a language is not regular.

Suppose you take a DFA for the language. We take an infinite set of strings such that all of them go to a different state. Then it’s obvious that the DFA cannot be finite and hence, it is not a DFA.

Example:

$$\begin{align} L &= {0^n1^n | n \ge 0} \ M &= \left(Q, \Sigma, \delta, q_0, F\right) \ L &= L\left(M\right) \ W &= {0^i | i \ge 0} \end{align}$$

We claim that any two strings in $W$ reach a different state.

Proof:

$$\begin{align} \hat{\delta}\left(q_0, 0^i\right) &\ne \hat{\delta}\left(q_0, 0^j\right) \forall i \ne j \ \hat{\delta}\left(q_0, 0^i1^i\right) &= \hat{\delta}\left(\hat{\delta} \left(q_0, 0 ^i\right), 1^i\right) \ &\ne \hat{\delta}\left(\hat{\delta}\left(q_0, 0^j\right), 1^i\right) \end{align}$$

If this wasn’t true then both the strings will be accepted, which is impossible according to the language.

Distinguishability

Defn: Let $L \subseteq \Sigma^$ be a language. Two strings $x,y \in \Sigma^$ are said to be distinguishable by $L$ if $\exists z \in \Sigma^*$ s.t. $xz \in L$ and $yz \notin L$.

Defn: A set $S$ is distinguishable if $\forall i \ne j \in S$ and $i$ and $j$ are distinguishable.

Theorem: Let $L \subseteq \Sigma^*$ be a regular language and $S$ be a distinguishable set. For any DFA accepting $L$, $\left|Q\right| \ge \left|S\right|$.

Myhill-Nerode Relations

An equivalence relation $\equiv$ over a language $L \subseteq \Sigma^*$ is said to be a Myhill-Nerode relation if

1. $\equiv$ is a right congruence, i.e., if $x \equiv y$, then $x\sigma \equiv y\sigma \forall \sigma \in \Sigma$.
2. $\equiv$ is a refinement of $L$, i.e., if $x\equiv y$ then $x\in L \iff y\in L$.
3. $\equiv$ is of finite index.

If $L$ is regular and $M = \left(Q,\Sigma, \delta, q_0, F\right)$ accepts M, then $\equiv_M$ is a Myhill-Nerode relation. It is trivial to see why this is the case.

We define $\equiv_M$ to be the equivalence relation gotten when any two strings end up in the same equivalence class in the language accepted by $M$ i.e. $\hat{\delta}\left(q_0, x\right) = \hat{\delta}\left(q_0, y\right)$.

We define $\equiv_L$ to be the equivalence relation gotten when any two strings $x$ and $y$ s.t. $\forall z \in \Sigma^*, xz \in L \Longleftrightarrow yz \in L$.

Theorem: Let $\equiv$ be an MH relation over $L$.

Then $\equiv \subseteq \equiv_L$.

Proof:

$$\begin{align} &\forall x,y, x\equiv y \ &\forall \sigma \in \Sigma, x\sigma \equiv y\sigma \ &\forall z \in \Sigma^* , \implies \left(xz \in L \iff yz\in L\right) \ &\implies x\equiv_L y \end{align}$$

Minimizing DFAs and Isomorphism

Let $M = \left(Q,\Sigma, \delta, s, F\right)$ and $M' = \left(Q', \Sigma, \delta', s', F' \right)$

Let $f: Q\rightarrow Q'$ be a bijection such that the following hold:

1. $s' = f(s)$
2. $q\in F \Longleftrightarrow f(q) \in F'$
3. $f(\delta(q,\sigma)) = \delta'(f(q), \sigma) \forall q \in Q, \sigma \in \Sigma$

Theorem: If $M$ and $M'$ are two minimal automatas then they are isomorphic.

Proof:

We define the function $f^{-1}: Q' \rightarrow Q$ to be $\hat{\delta}(s, x)$

Algorithm to minimize the DFA:

States $q, q' \in M$ are equivalent if $\forall x\in \Sigma^*, \hat{\delta} (q,x) \in F \Longleftrightarrow \hat{\delta}(q', x) \in F$

This is clearly an equivalence relation for the states.

Show that the Myhill-Nerode relation of the Quotient Automata $M_{/\approx}$ is a superset of the other. Hence the quotient automata is the minimal one.

Algorithm:

Mark any two pairs of states that are clearly not equivalent (one of them is a final state, other is not).

Repeat until no new pairs are marked

If $\exists {p,q}$ s.t. for some $\sigma \in \Sigma$, ${\delta(p,\sigma), \delta(q,\sigma)}$ are marked then mark ${p,q}$

Go to pattern matching

Context free languages

Productions: A kind of statement that tells you substitution rule.

Non-terminal strings are strings that can be replaced using productions.

Terminals are ones that can’t be further replaced.

Therefore, CFG is a 4 tuple that is defined using $\left(N, \Sigma, P, S\right)$

• $N$ is the set of non-terminals (RHS in any production).
• $\Sigma$ set of terminals
• $P$ set of production girls
• $S$ start symbol

E.g. $L = {0^n1^n| n \ge 0}$

$S \rightarrow 0S1 | \epsilon$

• A string $\beta \in (N \bigcup \Sigma^* )$ is derivable from $\alpha \in (N\bigcup \Sigma)^*$ if there is a production rule to substitute a non-terminal in $\alpha$ and get $\beta$.
• A string in $(N\bigcup\Sigma)^*$ is known as a sentential form if it is derivable from S.
• A string in $\Sigma^*$ is a sentence if it is derivable from $S$.

Example: Dyck language (balanced parentheses)

[[][[]][[]]] is in L but []] is not

$S \rightarrow [S] | SS | \epsilon$

Theorem: For a regular language $L$, there exists grammar $G$ s.t. $L = L(G)$

Construction:

$$\begin{align} \exists M = \left(Q,\Sigma, \delta, q_0, F\right) \ L(M) = L \ N = {S_i | q_i \in Q} \ S_i \rightarrow \sigma S_j \forall \delta(q_i, \sigma) = q_j \ q_i \in F \implies S_i \rightarrow \epsilon \ \end{align}$$

Further proof:

1. $L(M) \subseteq L(G)$

if $\hat{\delta}\left(q_i, w\right) = q_j$ then $S_i$ goes to $wS_j$

Base case: $\hat{\delta}(q_i, \epsilon) = q_0$ then $S_i \rightarrow S_i$

$\hat{\delta}(q_i, \sigma) = q_j$ then $\exists$ productions $S_i \rightarrow \sigma S_j$

2. $L(G) \subseteq L(M)$

induct on the length of the derivation

Ambiguous CFGs

These are those for which there are more than one parse trees. It is ambiguous if it has more than one leftmost derivation. Use multiple rules to resolve amiguousness.

However some languages are inherently ambiguous.

$a^ib^jc^kd^l | i = j \land k = l \lor i = l \land j = k$

basically no possible grammar can make it unambiguous.

Closure properties

Closed under union, concatenation, kleene closure.

NOT CLOSED under intersection and complementation.

Chomsky Normal form

A CFG G is in CNF if every production is of the form $A\rightarrow BC$ or $A\rightarrow \sigma$

CNF grammars do not generate $\epsilon$

• Remove $A\rightarrow \epsilon$

  • For every production $B\rightarrow \alpha A\beta$, add $B\rightarrow \alpha\beta$

• Remove $A\rightarrow B$

  • $B\rightarrow \beta$ with $A\rightarrow \beta$

First remove all the $\epsilon$ productions as they give more unit productions.

Then remove all unit productions.

This gives the minimum size grammar in CNF.

Pumping Lemma

This is based on the fact that (almost) all languages are convertible to CNF. If we have a path from the root node $S$ to a leaf node in the parse tree that is greater than $n +1$, i.e., $|w| > 2^{n+1}$ where $w$ is the length of the string and $n$ is the number of non-terminals in the productions.

By PHP, we can clearly see that a symbol is going to be repeated. So we can repeat the entire length in the path, and the parse tree will still be valid. This is the pumping we do.

For every CFL $L, \exists k > 0$ s.t. $\forall z \in L$ s.t. $|z| \ge k, \exists u,v,w,x,y$ s.t. $z = uvwxy$ with $vx \ne \epsilon$ and $|vwx| \le k$ s.t. $\forall i \ge 0 uv^iwx^iy \in L$.

Contrapositive form:

If $\forall k > 0, \exists z \in L; |z| \ge k$ s.t. $\forall u,z,w,x,y$ with $vx \ne \epsilon$ and $|vwx \le k$ s.t. $z=uvwxy$, $\exists i\ge 0$ s.t. $uv^iwx^iy \notin L$ then L is not context—free.

Prover and Spoiler:

• Prover picks k > 0

• Spoiler chooses the string $z$

• Prover chooses a split that he wants

• Spoiler finds the i for which pumped string is outside the language.

Parsing Algorithms for CFGs — Cocke Kasami Younger

Assumptions: G is in CNF

Goal: Given $w \in \Sigma^*$, check if $S \xrightarrow{\text{ * }} w$

$w = w_1w_2w_3\dots w_n$

$\exists A, B$ s.t. $S\rightarrow AB, A \xrightarrow{\text{ * }} w_1w_2 \dots w_i, B \xrightarrow{\text{ * }} w_{i+1} w_{i+2} \dots w_n$ for some $1 \le i \le n$

Try out all possible choices of $i$ and check if $A$ and $B$ match. This is done recursively.

Push Down Automata (non-deterministic)

Basically and NFA with a stack and a stack alphabet.

$M = \left(Q, \Sigma, \Gamma, \delta, s, \perp, F\right)$

These are in the order = start state, alphabet of the string, alphabet of the stack (string alphabet + non-terminals), transition function, initial state of the stack, and the final states.

$\delta \subseteq \left(Q\times \Sigma\cup {\epsilon}\times \Gamma\right) \times \left(Q\times \Gamma^*\right)$

If $\left(q, \sigma, A\right), \left(q', B_1B_2B_3\dots B_k\right) \in \delta$ then we read $\sigma$ from the string, pop $A$ from the stack, and push all of $B_1B_2\dots B_k$

If $\left(q, \epsilon, A\right), \left(q', B_1B_2B_3\dots B_k\right) \in \delta$ Read nothing but do the pushing and the popping.

Acceptance happens when it reaches a final state on reading the entire string.

Alternatively, empty stack acceptance happens when the string becomes empty and makes the stack empty as well.

Converting CFGs to PDAs

$G = \left(N, \Sigma, P, S\right)$

Define $\Gamma = N\cup\Sigma\cup{\perp}$

For a production $A \rightarrow \alpha$, add stack transition $\epsilon, A \rightarrow \alpha$

Add transition $\epsilon, \perp \rightarrow S$

Add transition $\sigma, \sigma \rightarrow \epsilon$

This PDA obviously accepts the CFG using empty staack acceptance as a basis.

Converting from PDAs to CFGs

TL;DR: Absolute pain in the ass

If you have a PDA with a single state that accepts using an empty stack:

If $\left(\left(q,\sigma, A\right), \left(q, B_1B_2\dots B_k\right)\right) \in\delta$ then add the production $A\rightarrow\sigma B_1B_2\dots B_k$

Nothing pushed on the stack case needs to be handled separately.

To convert a general PDA with a single final state to a PDA that accepts with the empty stack:

Let $M = \left(Q, \Sigma, \Gamma, \delta, s, \perp, {f}\right)$

We define $M' = \left({q}, \Sigma, \Gamma', \delta', {q}, \left(s, \perp, f\right), \phi\right)$

Here $\Gamma' = Q\times\Gamma\times Q$

Over here, both the Q’s are guesses for us, and we keep on guessing the entire sequence of things that are happening and put it on the stack. So we have an exponential number of items pushed onto the stack.

Suppose you are at state $p$ with $\sigma$ on the input string and the contents on the top of the stack were $A$. You transition to $q$ and the stack is now $B_1B_2\dots B_k$. For each of those you add a guess to the new PDA stack with surrounding states $pB_1q_1$ and so on upto $q_{k-1}B_kq_k$. Here $q_k$ is equal to $q$.

Effective Computability

Multiple notions of effective computability:

• $\lambda$ calculus
• $\mu$ recursive functions
• Turing Machines

Church Turing thesis: Any physically reaslisable computationally device can be simulated by a Turing machine.

Turing Machines

$M = \left(Q, \Sigma, \Gamma, \vdash, \circ, \delta, s, t, r\right)$

These are in the order state, string alphabet, tape alphabet, left end of the tape, blank symbol on the tape, transition, accept state and reject state.

$\delta: Q\times \Gamma \rightarrow Q\times\Gamma\times{L,R}$ where the first parentheses denotes the current state and the current symbol under the tape.

The right parentheses tells you the next state to go to, and the symbol to be written, and whether to move left or right.

Constraints:

• If you are on the left delimiter of the tape you can only move to the right.
• If you are on the accept/reject states, you are stuck there.

Configurations of a Turing Machine: $Q\times \Gamma^* \times \mathbb{N}$. These are, in order, current state, tape content, and the position of the tape head.

• Initial contents are $\left(s, \vdash x, 0\right)$
• Acceptance happens when $\left(s,\perp x, 0\right) \xrightarrow{\text{ * }} \left(t, y, m\right)$
• Rejection happens when $\left(s, \perp s, 0\right) \xrightarrow{\text{ * }} \left(r, y, n\right)$

An accepted language by a turing machine is called recursively enumerable (re). If it is a total turing machine then it is called recursive.

A total turing machine is one that eithers accepts a string or rejects a string. There is no string on which it never accepts and never rejects. (Basically loops forever on the tape)

A Multi tape turing machine, as it sounds, is a Turing Machine with multiple tapes. It is also possible to simulate a multi tape turing machine using a Turing Machine with a single tape.

Rough outline of how it happens:

• The number of tapes is $k$, and the number of states is $S$, and the size of the alphabet is $|\Sigma|$.
• Our new Turing Machine has $\left|\Sigma\right|^k$ pre filled tape cells.
• The tape alphabet is also enlarged similarly.
• The characters are now encoded in the new tape in such a way that it contains all possible combinations of the first tape characters in index 0, second tape characters in index 1, and so on.
• Finally, in a transition, it sweeps across the entire tape and finds where the character is.
• Once that happens, the tape head sweeps backwards to update the letters that were updated.

A Universal Turing Machine has 3 tapes, one for the encoding of the TM it is trying to simulate, one for the tape of TM it is simulating, and one to store the states and positions of said turing machines.

Theorem: $\exists$ a universal TM

Membership Problem: Given a TM $M$ and $x$, check if $M$ accepts $x$.

The language of this problem is r.e. (this is a fact).

Halting Problem: Check if $M$ halts on $x$.

The language of this problem is r.e. (this is a fact).

Property: If $L$ is both r.e. and co-r.e., then it is recursive. (co-r.e. means complement is recursive)

Proof: Simulate both on a single turing machine. Whichever accepts, halt and accept/reject accordingly.

Enumeration Machines

These have no input, there is no need to halt, one work tape and one output tape, there is a special print state that prints the contents of the output tape, clears it and then exits the state.

A language is r.e. iff there exists an E.M. for it. This is equivalent to a time sharing simulation of M.

Undecidability and Diagonalization

Theorem(Turing): HP is not recursive.

Let $M_x$ be the Turing Machine that is encoded by the string $x$. If no such thing exists, then let it be the trivial TM accepting everything.

This way, we get a list of turing machines. Let us assume that this is the complete list of turing machines.

Now consider a 2D matrix containing strings $y$ in the row header and TMs $M_x$ in the column header. The cell says H if the machine halts on the string and L if it loops forever. If our assumption that the list of turing machines being complete is true, then we can always do this table.

Suppose there is a universal Turing machine $K$ that halts and accepts if $M$ halts on $x$ and halts and rejects if $M$ loops on $x$.

Consider a universal machine $N$ that takes input $x$ and runs $K$ on $(M_x,x)$. If $K$ rejects the input then $N$ accepts it and if $K$ accepts it then $N$ goes into a loop.

If $N$ halts on $x \Longleftrightarrow K$ rejects $(M_x,x) \Longleftrightarrow M_x$ loops on $x$. This implies that $N$ differs from each row of the table at the diagonal. However the list contained every Turing Machine in existence, so the assumption that the table entries are determinable is wrong.

Reductions

If a problem $A$ is solvable by making a subroutine call to another problem $B$, we say that the problem $A$ is reducible to another problem $B$.

Basically all the following are equivalent:

• if B is True:
    A is True
  else:
    A is False
  

• $A$ is reducible to $B$

• $A \le_m B$

• $A$ can be solved by a subroutine call to $B$

Many-one reductions can be used to prove that something is not recognizable (or vice-versa). In that case only one subroutine call is allowed and the result has to be passed as-is by the outer machine.

In case you are generating a description of a machine from the input machine, the function that you use to generate the description must be computable and total.

Also, if $A \le_m B$, then $\bar{A} \le_m \bar{B}$.

Turing reductions are more lax in their rules, allowing multiple subroutine calls and modifying the output. However, they can only be used to demonstrate recursiveness (or the lack of it).

Examples of undecidable problems

Given a TM $M$ and a string $x$, decide if $M$ accepts $x$.

Proof:

Create a turing machine $H$ that takes input $M,x$ and decides whether $M$ accepts $x$.

Create a machine $D$ that does the opposite of what $H$ does when given input $M,M$

$D$ with the input $D$ will cause a contradiction.

Therefore $H$ cannot exist.

Undecidability of the Halting Problem using Reduction from TM acceptance

Proof:

If $H$ tell you that it halts, then we can run the simulation in a universal turing machine and see the acceptance. If $H$ tells you that it doesn’t halt, then you can say no for acceptance. Therefore, if the halting problem is solvable, then the acceptance problem is also solvable. But we know for a fact that acceptance problem isn’t solvable.

Check if a language of a turing machine is empty being undecidable

Proof:

We modify the machine $M$ and create a machine $M_1$.

If $L(M)$ is empty, then it returns false. If $L(M)$ is non-empty, then it checks if $w$ is in the language or not.

We use the description of $M_1$ to feed into the checker for $E_{TM}$ that checks if the language is empty or not. Inverting the output of the checker can give us the output of the checker of Acceptance problem.

Note that the checker for $E_{TM}$ need not necessarily run the machine description. It only deduces that based on some heuristics that are not our concern. We do not have to find the machine that does that, only prove it does not exist. For which we assume the contrary.

Check if a a language of a turing machine is regular or not being undecidable

Proof:

We have a machine $R_{TM}$ that decides whether a TM description is regular or not.

We need to create a machine $A_{TM}$ that decides whether the input $(M,x)$ will be accepted or not.

We create $M_1$ from $(M,x)$ and runs $M$ on $x$ and gives us “true” if the input to $M_1$, i.e. $y$ has the form $0^n1^n$ else it gives “true” if $M$ gives “true” on $x$.

Carefully observe what this is doing. When $M$ accepts $x$, its language is $\Sigma^*$, otherwise it is $0^n1^n$. So the regular language decider will give “true” if $M$ accepts $x$ and “false” otherwise.

We feed this description of $M_1$ to the decider $R_{TM}$ and use the output as the output of $A_{TM}$.

Proof of two machines having equal languages being undecidable

Suppose a decider for the above problem exists. It takes $M_1,M_2$ and gives “true” if they are equal. Run it with $M, M_1$ where $M_1$ rejects everything and $M$ is the input to the decider of the empty language problem will solve the empty language problem.