Automata Notes

Published on the


Deterministic Finite Automata

Chomsky Hierarchy

Type Automaton Language
0 Turing Machines Recursively Enumerable
1 Linear-bounded Turing Machines Context-sensitive
2 Pushdown Automata Context-free
3 Finite Automata Regular

Production Rules

\[ S \to \mathsf{0}M \] \[ A \to \mathsf{1}B \] \[ B \to \mathsf{0} \] \[ B \to \mathsf{1}B \]


Pushdown Automata

Turing Machines

Computable Numbers

The Halting Problem

Proposition: There exists no Turing machine which takes the description number of a Turing machine, \(M\) and its input \(I\) on its tape and can determine whether \(M\) will halt on \(I\).

Proof: Suppose there were such a Turing machine. Then it would be possible to construct another Turing machine, \(K\), that takes the description number of a Turing machine \(M\). If \(M\) halts on \(M\), then \(K\) doesn’t halt. If \(M\) doesn’t halt on \(M\), \(K\) does halt. Now execute \(K\) on \(K\). If \(K\) halts on \(K\), then \(K\) doesn’t halt on \(K\). If \(K\) doesn’t halt on \(K\), then \(K\) halts on \(K\). Thus, we have arrived a a contradiction. Hence, our original assumption must be incorrect.

Rice’s Theorem

Proposition: All non-trivial semantic properties of Turing machines are undecidable.

Proof: Suppose there exists a non-trivial semantic property of Turing machines that is decidable, let us call that property \(P\) and let us the call the Turing machine that can decide this property \(M\). There must exists some Turing machine that satisfies the property \(P\), let us it \(K_1\). Clearly inputting \(K_1\) to \(M\) will result in acceptance. Let us create a new Turing machine \(K_2\) which computes \(K_1\), but before this simulates some arbitrary Turing machine \(h\) on some arbitrary input \(i\). Provided \(h\) halts on \(i\) then, \(K_2\) behaves identically to \(K_1\). In other words, \(M\) will accept on \(K_2\) provided \(h\) halts on \(i\). Thus, \(M\) must know if \(h\) will halt on \(i\). Therefore to solve the halting problem, \(K_2\) can be constructed for the Turing machine \(h\) and its input \(i\), and this can be fed into \(M\), if \(M\) halts, then it is known that \(h\) halts. Thus the halting problem is solved. However, we know that the halting problem cannot be solved, therefore we have reached a contradiction. Hence, our original assumption must be wrong.

Busy Beaver Function

Proposition: The busy beaver function \(\Sigma\) is uncomputable.

Proof: Suppose there were a Turing machine to compute the busy beaver function for \(n\)-state Turing machines, called \(A\). We shall assume \(A\) begins by writing \(n\) on its tape, in binary. This means \(A\) has \(\ceil{\log_2 n + k}\) states, where \(k\) is a constant. However, in order to differentiate the binary pattern, from the rest of the tape, since only the binary alphabet is permitted, we shall encode the binary number with 1s between each digit. So \(A\) will have \(2\ceil{\log_2 n} + k_1\) states. We can also construct a Turing machine \(B\) that reads the input from \(A\) and prints that many ones, suppose \(B\) requires \(k_2\) states, where \(k_2\) is a constant. We can combine these machines, to create a machine \(AB\), that has \(2\ceil{\log_2 n} + k_1 + k_2\) states. There will eventually some value for \(n\) for which \(n \ge 2\ceil{{\log_2}^n} + k_1 + k_2\) states. Therefore for that value of \(n\) we will have created a machine with less states, that prints the same number of 1s. This, of course, cannot be, because then there will be a Turing machine with \(n\) states, that prints more 1s than \(\Sigma(n)\). Hence we have reached a contradiction, and our original assumption must be wrong.

Proposition: For any computable function \(f\), there exists \(n \in \mathbb{N}\), such that \(\forall x\;(x \ge n \to \Sigma(n) > f(n))\).

Proof: Suppose this were not true. Then there would exist some function \(f\) and number \(n \in \mathbb{N}\), after which \(\forall x\;(x \ge n \to f(n) > \Sigma(n)\). However, this would mean \(\Sigma(x)\) could be computed, where \(x \ge n\). Since \(f\) provides an upper bound for the number of steps the \(n\)-state busy beaver Turing machine would have to perform. We know that \(\Sigma(n)\) is uncomputable, therefore we have reached a contradiction. Hence, out original assumption must be wrong.

Church-Turing Thesis