Turing machines, decidability and undecidability notes — Unit 5

In 1936, Alan Turing invented a theoretical mathematical machine to define exactly what "computation" means. The Turing Machine is the most powerful computational model in existence.

It is widely accepted (The Church-Turing Thesis) that ANY algorithm that can be computed by ANY physical computer in the universe (including quantum computers) can be mathematically simulated by a simple Turing Machine.

⇒1.1 Anatomy of a Turing Machine

A TM has three basic components:

• An Infinite Tape: The memory. The tape is divided into discrete cells. It extends infinitely to the left and infinitely to the right. Initially, it contains the input string, padded by infinite Blank symbols ($B$) on both sides.
• A Read/Write Head: A physical scanner that hovers over exactly one cell of the tape at a time. Crucially, it can move Left or Right, allowing the machine to revisit old memory arbitrarily.
• A Finite Control (CPU): Contains the states and the transition logic, dictating what the machine should do based on its current state and the symbol the head is looking at.

A Turing Machine is formally defined as a 7-tuple:
$M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$

• $Q$: A finite set of states.
• $\Sigma$: The input alphabet (symbols originally on the tape).
• $\Gamma$: The Tape Alphabet. The set of all symbols the machine can physically write to the tape. Note that $\Sigma subset \Gamma$.
• $q_0$: The initial state.
• $B$: The Blank symbol. $B \in \Gamma$ but $B \notin \Sigma$.
• $F$: The set of final accepting states.

⇒2.1 The TM Transition Function

The brain of the TM is defined as:
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$

When the machine is in state $q$ and reads symbol $X$ under the head, the function tells it to do THREE things simultaneously:

• 1. Enter a new state $p$.
• 2. Overwrite the symbol $X$ on the tape with a new symbol $Y$.
• 3. Physically move the Read/Write head exactly one cell to the Left ($L$) or Right ($R$).

A PDA cannot solve $a^n b^n c^n$ because it loses count. A TM solves it easily by bouncing back and forth across the tape.

⇒3.1 The Algorithm

Tape contains: `a a b b c c B B B...`

• 1. Start at the left. Read an 'a'. Overwrite it with an 'X' to mark it as counted. Move Right.
• 2. Scan right, ignoring all other 'a's, until you find the first 'b'. Overwrite it with a 'Y'. Move Right.
• 3. Scan right, ignoring other 'b's, until you find the first 'c'. Overwrite it with a 'Z'.
• 4. Now move the head LEFT continuously, ignoring everything, until you hit the 'X' you wrote in step 1.
• 5. Move one cell right. You are now at the next uncounted 'a'. Repeat the whole process.
• 6. If you eventually mark all 'a's, 'b's, and 'c's perfectly, and hit the Blank symbol $B$, ACCEPT the string.

Because the TM can move left and overwrite memory, it can execute arbitrary loops and algorithms, unlike a PDA.

Computer scientists have invented massive, seemingly overpowered upgrades to the standard Turing Machine. However, deep mathematical theorems prove that none of these upgrades add any actual computing power. A standard, single-tape deterministic TM can mathematically simulate all of them.

⇒4.1 Multi-Tape Turing Machine

Has a CPU with 5 separate infinite tapes and 5 separate read/write heads that can move independently.
Equivalence: A standard single-tape TM can simulate it by dividing its single tape into 10 parallel "tracks" (5 for data, 5 to mark where the heads are) and running back and forth to update them.

⇒4.2 Nondeterministic Turing Machine (NTM)

Like an NFA, an NTM can magically guess and branch its computation into infinite parallel realities. If ANY reality accepts, the NTM accepts.
Equivalence: A deterministic TM can simulate an NTM by executing a massive Breadth-First Search across all possible reality branches. It might take billions of years, but it WILL eventually compute the exact same mathematical answer. Therefore, Deterministic TM $\equiv$ Nondeterministic TM.

Noam Chomsky classified all formal languages and computing machines into a strict mathematical hierarchy of power.

• Type 3 (Regular Languages): The weakest. Generated by Regular Grammars. Recognized by DFAs/NFAs. (Cannot count).
• Type 2 (Context-Free Languages): Generated by Context-Free Grammars. Recognized by Pushdown Automata (PDA). (Can count, but only via a single stack).
• Type 1 (Context-Sensitive Languages): Generated by Context-Sensitive Grammars. Recognized by Linear Bounded Automata (LBA - a TM where the tape is strictly finite, bounded by the input length).
• Type 0 (Recursively Enumerable Languages): The absolute limit. Generated by Unrestricted Grammars. Recognized by Turing Machines.

Type $3 subset$ Type $2 subset$ Type $1 subset$ Type $0$. Every regular language is context-free, but not vice-versa.

Turing Machines introduce a terrifying third outcome to computation. A DFA always finishes reading a string and HALTS (accepts or rejects). A Turing Machine can get stuck in an infinite loop and run forever.

⇒6.1 Recursively Enumerable (RE) Languages

A language is RE if there exists a Turing Machine that will Accept all valid strings. However, if you feed it an INVALID string, the machine might Reject it, OR it might enter an infinite loop and never halt. You will never know if it's taking a long time, or if it's broken.

⇒6.2 Recursive Languages (Decidable)

A stronger, much safer classification. A language is Recursive if there exists a Turing Machine that is mathematically guaranteed to HALT on every single possible input. It will definitely Accept valid strings, and it will definitely, eventually Halt and Reject invalid strings. It never loops infinitely.

Algorithm = Turing Machine that is guaranteed to Halt. Therefore, we only care about Recursive languages.

A computational problem is defined as a question that asks for a "Yes" or "No" answer. (e.g., "Is this graph connected?")

⇒7.1 Decidable Problems

A problem is Decidable if there exists an Algorithm (a Turing Machine that is guaranteed to halt) that can output YES or NO for any valid input.

Almost everything we program daily is decidable.

⇒7.2 Undecidable Problems

A problem is Undecidable if it is mathematically impossible to construct a Turing machine that will always halt and give a correct YES/NO answer for every possible input.
This means the problem is fundamentally, universally unsolvable by any computer that will ever be built in the universe.

The most famous undecidable problem in history, proven by Alan Turing in 1936.

⇒8.1 The Question

Given the source code of an arbitrary computer program $P$, and an input $I$, can you write a super-program called `WillHalt(P, I)` that correctly analyzes the code and outputs YES (the program will eventually finish) or NO (the program contains an infinite loop and will freeze)?

Every programmer wishes `WillHalt` existed. It would instantly detect all infinite loops during compilation.

⇒8.2 The Proof by Contradiction

Turing proved `WillHalt` cannot exist by creating a paradox.

1. Assume `WillHalt` works perfectly.

2. Write a malicious program called `Paradox(P)`:
```c
void Paradox(Program P) {
if ( WillHalt(P, P) == YES ) {
while(true) {} // intentionally loop forever
} else {
return; // intentionally halt
}
}
```

What happens if we feed the `Paradox` program its own source code as input? What happens when we run `Paradox(Paradox)`?

• Case 1: `WillHalt` analyzes it and says YES, Paradox WILL halt.
  According to our code, if `WillHalt` returns YES, the `Paradox` program deliberately enters an infinite loop. So `WillHalt` was wrong.
• Case 2: `WillHalt` analyzes it and says NO, Paradox will loop forever.
  According to our code, if `WillHalt` returns NO, the `Paradox` program immediately returns and halts. So `WillHalt` was wrong again.

Conclusion: The `WillHalt` super-analyzer is mathematically flawed. It is trapped in a logical paradox (like "This sentence is false"). Because this paradox destroys the logic, Turing proved that building a universal infinite-loop detector is mathematically impossible.

The Halting Problem is strictly Undecidable.

Another classic Undecidable problem, invented by Emil Post. It proves that undecidability isn't just about infinite loops; it applies to simple puzzle-solving.

⇒10.1 The Puzzle

You are given a finite set of dominoes. Each domino has a string printed on the Top half, and a string on the Bottom half. You have an infinite supply of each domino type.

Domino 1: Top = `b`, Bottom = `bb`
Domino 2: Top = `ab`, Bottom = `a`
Domino 3: Top = `a`, Bottom = `ab`

The Question: Can you arrange a sequence of these dominoes side-by-side such that the string formed by reading all the Top halves matches EXACTLY with the string formed by reading all the Bottom halves?

⇒10.2 Undecidability

While you can easily write a program to brute-force search for a match, if no match exists, your program will search forever. There is no algorithm that can analyze an arbitrary set of dominoes and definitively output "NO, a match is impossible" in a finite amount of time. PCP is Undecidable.

Unit 5 concludes the degree syllabus by defining the absolute mathematical boundaries of what a computer can and cannot do.

⇒11.1 University Exam Checklist

• Write the formal 7-tuple definition of a Turing Machine. Explain the role of the infinite tape and the Read/Write head.
• Draw a complete Turing Machine transition diagram to accept the language $L = \{0^n 1^n 2^n\}$ or $L = \{ww\}$.
• Discuss the Church-Turing Thesis.
• Explain why a Multi-Tape Turing Machine or a Nondeterministic Turing Machine is NOT mathematically more powerful than a standard single-tape TM.
• Draw the Chomsky Hierarchy, listing the four Grammars, their corresponding Languages, and their corresponding computing Automata.
• Explain the critical difference between a Recursively Enumerable language and a Recursive (Decidable) language.
• What does it mean for a computational problem to be Undecidable?
• State the Halting Problem. Replicate Turing's proof by contradiction (the `Paradox` code) to prove it is undecidable.
• Explain Post's Correspondence Problem (PCP) with an example of dominos.