Automata and Computability

Formal definition. A DFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q$ is a finite set of states
• $\Sigma$ is a finite alphabet (input symbols)
• $\delta: Q \times \Sigma \to Q$ is the transition function
• $q_0 \in Q$ is the start state
• $F \subseteq Q$ is the set of accepting (final) states

Language accepted: $L(M) = \{w \in \Sigma^* \mid \hat{\delta}(q_0, w) \in F\}$

Where $\hat{\delta}$ is the extended transition function (processes entire string).

$M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q = \{S, A, B\}$ (S = start, A = saw 0, B = saw 01)
• $\Sigma = \{0, 1\}$
• $F = \{B\}$

Trace for “1101”: S → S → A → B. Accepted. ✓

Trace for “1001”: S → S → A → S → A →… Wait, let me retrace.

“1001”: S -(1)→ S -(0)→ A -(0)→ A -(1)→ B. Accepted. ✓

Formal definition. An NFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $\delta: Q \times \Sigma \to \mathcal{P}(Q)$ (maps to a set of states, not a single state)
• All other components are the same as a DFA

An NFA accepts a string if there exists at least one path through the machine that ends in an Accepting state.

An ε-NFA additionally allows transitions on the empty string ε (changing state without consuming Input).

$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$

Theorem (Rabin-Scott). For every NFA $N$There exists a DFA $D$ such that $L(N) = L(D)$. DFAs And NFAs accept exactly the same class of languages (the regular languages).

Proof (subset construction). Given NFA $N = (Q_N, \Sigma, \delta_N, q_0, F_N)$Construct DFA $D = (Q_D, \Sigma, \delta_D, q_0", F_D)$:

1. $Q_D = \mathcal{P}(Q_N)$ (states are subsets of $Q_N$)
2. $q_0' = \varepsilon\mathrm{-closure}(\{q_0\})$
3. $\delta_D(S, a) = \varepsilon\mathrm{-closure}\left(\bigcup_{q \in S} \delta_N(q, a)\right)$ for $S \subseteq Q_N$
4. $F_D = \{S \subseteq Q_N \mid S \cap F_N \neq \emptyset\}$

The DFA tracks the set of all states the NFA could be in. Since $Q_N$ is finite, $Q_D$ is finite (at Most $2^{|Q_N|}$ states). The DFA accepts exactly the same strings as the NFA. $\square$

Corollary. The class of regular languages is closed under union, intersection, complementation, Concatenation, and Kleene star.

A regular expression defines a regular language using operators:

Kleene’s Theorem. A language is regular if and only if it can be described by a regular Expression.

Theorem. The language $L = \{a^n b^n \mid n \geq 0\}$ is not regular.

Proof (Pumping Lemma). The Pumping Lemma for regular languages states: if $L$ is regular, then There exists a pumping length $p$ such that any string $s \in L$ with $|s| \geq p$ can be split into $s = xyz$ where:

1. $|xy| \leq p$
2. $|y| \geq 1$
3. $xy^iz \in L$ for all $i \geq 0$

Choose $s = a^p b^p$. By condition 1, $y$ consists only of $a$‘s. Pumping ($i = 0$): $xz = a^{p-|y|}b^p$. Since $|y| \geq 1$, $p - |y| \neq p$So $a^{p-|y|}b^p \notin L$. Contradiction. $\square$

A Turing machine (TM) is a 7-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ where:

• $Q$ is a finite set of states
• $\Sigma$ is the input alphabet (does not include the blank symbol)
• $\Gamma$ is the tape alphabet ($\Sigma \subseteq \Gamma$Includes blank symbol $\sqcup$)
• $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function
• $q_0$ is the start state
• $q_{accept}$ is the accept state
• $q_{reject}$ is the reject state ($q_{reject} \neq q_{accept}$)

1. Tape is infinite in both directions, initialised with input followed by blanks
2. Read/write head starts at the leftmost input symbol
3. At each step: read the current symbol, consult $\delta$Write a symbol, move head left or right
4. Accept if $q_{accept}$ is reached; reject if $q_{reject}$ is reached; may loop forever

Algorithm:

1. If tape is empty, accept
2. Find the leftmost aReplace with XMove right to find the leftmost bReplace with X
3. Return to the leftmost remaining a
4. Repeat until no a remains
5. If only X’s and blanks remain, accept; otherwise reject

Formal transitions (partial):

Thesis (not provable — a thesis): Every effectively computable function is computable by a Turing machine.

Equivalently: any reasonable model of computation (lambda calculus, μ-recursive functions, modern Programming languages) can compute exactly the same set of functions as a Turing machine.

This is a thesis, not a theorem — it cannot be proven because “effectively computable” is an Informal concept. However, no counterexample has ever been found.

Halting problem: Given a description of a Turing machine $M$ and an input $w$Determine whether $M$ halts (accepts or rejects) when run on $w$.

Theorem (Turing, 1936). The halting problem is undecidable — no Turing machine can solve it For all possible inputs.

Assume a Turing machine $H$ exists that decides the halting problem:

$H(M, w) = \begin{cases} \mathrm{accept} & \mathrm{if } M \mathrm{ halts on } w \\ \mathrm{reject} & \mathrm{if } M \mathrm{ does not halt on } w \end{cases}$

Construct a new machine $D$ that uses $H$:

$D(M) = \begin{cases} \mathrm{loop forever} & \mathrm{if } H(M, M) = \mathrm{accept} \\ \mathrm{halt (reject)} & \mathrm{if } H(M, M) = \mathrm{reject} \end{cases}$

The contradiction: What happens when $D$ is run on its own description, $D$?

• If $D(D)$ halts → $H(D, D)$ accepted → $D$ should loop forever → contradiction
• If $D(D)$ loops forever → $H(D, D)$ rejected → $D$ should halt → contradiction

Both cases lead to contradictions, so $H$ cannot exist. $\square$

Corollary. The halting problem is semi-decidable (recursively enumerable): we can build a Machine that accepts when $M$ halts on $w$But it cannot always reject when $M$ doesn’t halt (it Would have to run forever).

• P: The class of decision problems solvable by a deterministic Turing machine in polynomial time $O(n^k)$ for some constant $k$.
• NP: The class of decision problems whose yes-instances can be verified by a deterministic Turing machine in polynomial time (given a certificate).

$\mathrm{P} \subseteq \mathrm{NP}$

Every problem in P is also in NP (if you can solve it in polynomial time, you can certainly verify a Solution in polynomial time).

The P vs NP question: Is $\mathrm{P} = \mathrm{NP}$? This is one of the seven Millennium Prize Problems. Most computer scientists believe $\mathrm{P} \neq \mathrm{NP}$.

A problem is NP-complete if:

1. It is in NP
2. Every problem in NP can be reduced to it in polynomial time

Examples of NP-complete problems:

• Boolean satisfiability (SAT)
• Travelling Salesman Problem (decision version)
• Graph colouring
• Knapsack problem
• Subset sum

Implication: If any NP-complete problem is in P, then $\mathrm{P} = \mathrm{NP}$.

Problem 1. Design a DFA that accepts all binary strings containing an even number of 0s. Give The formal definition and draw the transition table.

Problem 2. Convert the following NFA to a DFA using the subset construction.

NFA: States $\{0, 1, 2\}$Alphabet $\{a, b\}$Start state 0, accepting state 2.

Problem 3. Write a regular expression for the language of all binary strings that do NOT contain The substring “11”.

Problem 4. Use the Pumping Lemma to prove that $L = \{ww \mid w \in \{0,1\}^*\}$ is not regular.

Problem 5. Describe a Turing machine that decides whether a binary string is a palindrome (reads The same forwards and backwards).

Problem 6. Prove that if the halting problem were decidable, then every semi-decidable language Would be decidable.

Problem 7. Explain the difference between a decidable problem and a semi-decidable problem. Give An example of each.

Problem 8. Is the complement of the halting problem semi-decidable? Explain.

Problem 9. Explain why the Travelling Salesman Problem (decision version: “Is there a tour of Length ≤ k?”) is in NP.

Problem 10. State the Church-Turing thesis. Explain why it is a thesis and not a theorem. What Would it mean if it were false?

1. Misunderstanding the difference between a stack (LIFO) and a queue (FIFO) in data structure applications.

2. Confusing an algorithm with a program. An algorithm is a step-by-step procedure, not its implementation in code.

3. Neglecting to normalise database designs, leading to data redundancy and update anomalies.

4. Mixing up Big O, Big $\Omega$, and Big $\Theta$ notation. Big O is an upper bound, not necessarily tight.

1. Assuming NFAs are more powerful than DFAs. NFAs and DFAs accept exactly the same class of languages (the regular languages). NFAs are more convenient to write but not more powerful. The subset construction converts any NFA to an equivalent DFA.

2. Misapplying the Pumping Lemma. The Pumping Lemma shows a language is NOT regular by contradiction — you must show that for any pumping length p, there exists a string that cannot be pumped. Students often try to prove a language IS regular using the Pumping Lemma, which is impossible.

3. Confusing semi-decidable with decidable. The halting problem is semi-decidable — you can build a machine that accepts when it halts, but you cannot always reject when it doesn’t halt (it would loop forever). Decidable problems always halt with the correct answer.

4. Confusing P with NP. P is the class of problems solvable in polynomial time. NP is the class whose YES-instances can be verified in polynomial time. P ⊆ NP, but whether P = NP is unknown. NP-complete problems are in NP but not known to be in P.

5. Drawing NFA transitions incorrectly. An NFA can have multiple transitions for the same input symbol from a single state, and can have ε-transitions (changing state without consuming input). DFAs have exactly one transition per symbol per state.

The key principles covered in this topic are linked in the sub-pages above. Focus on understanding the definitions, applying the formulas or frameworks, and evaluating strengths and limitations of each approach.

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.

At its core, computability theory asks a deceptively simple question: what can a machine actually do? Imagine you have an infinitely powerful assistant who can follow instructions perfectly and never gets tired. The theory of computation draws a boundary around what that assistant could — and could not — accomplish, no matter how clever the instructions. Automata are the simplest models in this landscape: finite automata can only remember a limited amount of information (like a toggle switch), push-down automata add a stack for slightly more memory, and Turing machines get an unlimited tape. Each step up in power unlocks new categories of problems that become solvable.

The Church-Turing thesis ties this all together by claiming that the Turing machine — despite being a simple, mechanical device — captures everything we informally mean by “computable.” Think of it like this: if you can describe a step-by-step procedure that a human could follow with pencil and paper, then a Turing machine can simulate it. This is remarkable because it means all programming languages, no matter how fancy their features, are ultimately equivalent in computational power. The differences between languages are about convenience and efficiency, not about what they can fundamentally compute.

Some problems, however, remain beyond reach. The halting problem — determining whether an arbitrary program will eventually stop or run forever — is famously undecidable. No algorithm can solve it for all possible inputs, and this sets a hard ceiling on what automated tools can guarantee. This insight has real consequences: it explains why perfect bug detectors, perfect optimisers, and perfect type-checkers are impossible. Recognising these limits is just as important as understanding what machines can do.