Algorithms and the Limits of Computation

Turing Machine

2026-08-18 21:55

Where we are

What you already have

From Basics of a Turing Machine:

• the 6-tuple \(M = (Q, \Sigma, \Gamma, \delta, q_0, H)\)
• configurations and the yield relation \(\vdash_M\)
• the Universal Turing Machine \(U(\langle M, w \rangle)\)

Every construction there answered how. This unit asks whether.

Two loose threads

Halting. Nothing in the definition forces a machine to stop.

The head moves only where \(\delta\) sends it.

Universality. \(U\) simulates but does not decide.

If \(M\) loops on \(w\), then \(U\) loops too.

Both threads were planted deliberately at the end of the last unit. This unit is entirely about what lives in that gap.

What you will be able to do

1. Give the formal definition of an algorithm.
2. Distinguish Turing-decidable, Turing-semidecidable and Turing-computable.
3. State the Church-Turing thesis and say why it is a hypothesis.
4. Use a counting argument to show most problems are not even semidecidable.
5. Construct a diagonal language and prove no machine semidecides it.
6. Prove the Halting Problem unsolvable.
7. Use a many-one reduction to transfer unsolvability.
8. Decide whether a question about a machine is solvable.

From what machines do, to what they cannot

One big question

Are Turing machines powerful enough to model any conceivable algorithm?

To answer it we must first define algorithm.

The route

1. Define algorithm — it turns out to mean halts on every input.
2. Count, and find more problems than machines.
3. Diagonalize, and name a problem no machine solves.
4. Use self-reference to kill the Halting Problem.
5. Use reductions to spread unsolvability.

Each technique is sharper than the one before.

Existence, then a witness, then the famous one, then a method for producing more. Say this ordering out loud — it is the spine of the whole lecture.

What exactly is an algorithm?

The informal definition

An algorithm is an effective, systematic, mechanical method for achieving the desired result for a given problem.

Its properties:

1. A finite number of instructions.
2. Produces the result in a finite number of steps.
3. Can be carried out by a human with only paper and pen.
4. Requires no insight, intuition or ingenuity.

Clause 2 is load-bearing

Everything in this unit turns on terminates in finitely many steps.

Clause 3 is last unit’s analogy restated as a requirement — paper and pen is the tape and the head. Clause 4 is what “mechanical” has to mean for the definition to be useful.

Two kinds of problem

Decision problems — input \(w\), output yes or no.

Yes means \(w \in L\). Given a chess configuration and it is your turn, can you win?

Function computation — input \(w\), output \(f(w)\).

Given the Facebook graph, what is the minimum number of people between you and your role model?

Decidable, semidecidable, computable

Turing-decidable

\(M\) decides \(L \subseteq \Sigma^*\) iff for all \(w \in \Sigma^*\):

\[\begin{cases} M \text{ accepts } w, & \text{if } w \in L, \\ M \text{ rejects } w, & \text{if } w \notin L. \end{cases}\]

A language is Turing-decidable, or recursive, iff some TM decides it.

Every input gets a verdict. Nothing runs forever.

Turing-computable

\(M\) computes \(f : \Sigma^* \to \Sigma^*\) iff for all \(w \in \Sigma^*\):

\[(q_0, \triangleright w) \vdash^* (q_{\text{acc}}, \triangleright f(w))\]

Again: on every input.

Turing-semidecidable

\(M\) semidecides \(L\) iff for all \(w \in \Sigma^*\):

\[\begin{cases} M \text{ accepts } w, & \text{if } w \in L, \\ M \text{ rejects } w \text{ or runs forever}, & \text{if } w \notin L. \end{cases}\]

A yes answer arrives. A no answer may never arrive.

And you cannot tell the difference between “still running” and “will run forever”. This asymmetry is the single most important idea in the unit.

Which of these is an algorithm?

Type of computation	Always halt?
TM’s for decidable languages	✓
TM’s for computable functions	✓
TM’s for semidecidable languages	✗

Algorithm = a TM for a Turing-decidable language, or for a Turing-computable function.

The definitions that follow

• Algorithmic solvability — Turing-decidability or Turing-computability.
• Algorithmic unsolvability — Turing-undecidability or Turing-noncomputability.

Semidecidability is deliberately excluded.

A procedure that might not stop is not an algorithm — however useful it is in practice.

The confusion to avoid

“Semidecidable” does not mean “solvable if you are patient”.

If the machine has not accepted yet, you have learned nothing.

The Church-Turing thesis

The statement

Any algorithm can be executed by a Turing machine.

Equivalently:

• Anything that can be computed can be computed by a Turing machine.
• Turing machines can do anything describable as “purely mechanical”.

Why it cannot be proved

One side is formal — Turing machines.

The other side is informal — what a person or device could mechanically do.

No proof crosses that gap. What supports it is evidence: \(\lambda\)-calculus, register machines, every programming language — all compute the same functions.

Why we care

Without the thesis, “the Halting Problem is undecidable” is a fact about one formalism.

With it, it is a fact about computation.

Every “no algorithm exists” from here on is really “no Turing machine exists” plus this thesis. Say it once, then stop repeating it.

Two properties of the boundary

If \(L\) is Turing-decidable, then \(\overline{L}\) is Turing-decidable too.

Run the decider and swap the verdict.

If \(L\) is semidecidable and undecidable, then \(\overline{L}\) is not semidecidable.

Otherwise run both machines in parallel and always get an answer — making \(L\) decidable.

Counting machines against problems

The claim

The set of all decision problems is bigger than the set of all Turing machines.

Proved before naming a single unsolvable problem.

Part 1 — problems are uncountable

A decision problem is a function \(\Sigma^* \to \{0,1\}\) — read the answers off as bits.

Strings		\(\{0,1\}\)
\(\epsilon\)	→	0
0	→	1
1	→	1
00	→	0
01	→	0
10	→	0
11	→	1

This one is the number

\[0.0110001\ldots\]

• decision problems \(\leftrightarrow\) reals in \([0,1]\)
• the reals in \([0,1]\) are uncountable

Part 2 — machines are countable

• A TM can be represented as a finite string.
• A finite ASCII string is a binary string.
• The set of all binary strings is countable.

Every program in every language you will ever write is on that list.

The conclusion

An uncountable set cannot inject into a countable one.

Most decision problems are not even Turing-semidecidable.

Two caveats. This names nothing — that is the next section’s job. And “most” is far stronger than it sounds: the solvable problems are a vanishingly small subset. That we mostly meet solvable problems says something about human interests, not computation.

Diagonalization names a problem

The intuition first

To show a list is incomplete, you do not examine infinitely many entries.

You build one thing the list cannot contain.

How to defeat every entry at once

Build an object that differs from:

• entry 1 in the first place you look
• entry 2 in the second place
• entry \(i\) in the \(i\)th place

Then it cannot equal entry \(i\) for any \(i\).

The cost of defeating all of them is one disagreement each.

Why “diagonalization”

Lay the list out as a grid — machines down, inputs across.

Entry \(i\)’s behaviour is row \(i\). Position \(i\) is column \(i\).

So the places we disagree are the cells \((i,i)\) — the diagonal.

The name is literal.

This is Cantor’s argument that the reals outnumber the integers, reused with machines in place of numbers.

Step 1 — build the table

TM	\(w_1\)	\(w_2\)	\(w_3\)	\(w_4\)	\(w_5\)	\(\cdots\)
\(M_1\)	1	0	0	1	0	\(\cdots\)
\(M_2\)	0	0	1	0	0	\(\cdots\)
\(M_3\)	0	1	1	1	1	\(\cdots\)
\(M_4\)	1	1	0	1	0	\(\cdots\)
\(M_5\)	0	1	0	0	0	\(\cdots\)

Every semidecidable language is a row, because every machine appears.

Step 2 — read the diagonal, flip it

Diagonal: \(1, 0, 1, 1, 0, \ldots\)

Flipped: \(0, 1, 0, 0, 1, \ldots\)

\[L_d = \{w_i \mid w_i \notin L(M_i)\}, \qquad d_i = \begin{cases} 1 & \text{if } \text{table}_{ii} = 0, \\ 0 & \text{if } \text{table}_{ii} = 1. \end{cases}\]

Step 3 — ask the breaking question

Suppose \(L_d\) is semidecidable. Then \(L_d = L(M_k)\) for some \(M_k\).

Does \(M_k\) accept \(w_k\)?

Case 1 — \(M_k\) accepts \(w_k\)

\[\implies w_k \notin L_d \quad (\text{defn. of } L_d)\]

\[\implies w_k \notin L(M_k) \quad (L_d = L(M_k))\]

\[\implies M_k \text{ does not accept } w_k\]

Contradicts the assumption of this case.

Case 2 — \(M_k\) does not accept \(w_k\)

\[\implies w_k \in L_d \quad (\text{defn. of } L_d)\]

\[\implies w_k \in L(M_k) \quad (L_d = L(M_k))\]

\[\implies M_k \text{ accepts } w_k\]

Contradicts the assumption of this case.

Both branches contradict

\(L_d\) is not Turing-semidecidable.

We have named a specific decision problem no machine solves.

Loops, simulation, and the Halting Problem

Looping needs no complexity

Three machines over \(\Sigma = \{a\}\). Each has one state.

\(M_1\)	\(\triangleright\)	\(a\)	\(\square\)
\(q_0\)	\((q_0, \rightarrow)\)	\((q_0, \rightarrow)\)	\((q_0, \rightarrow)\)

The head keeps moving right forever.

Two more that never halt

\(M_2\)	\(\triangleright\)	\(a\)	\(\square\)
\(q_0\)	\((q_0, \rightarrow)\)	\((q_0, a)\)	\((q_0, \square)\)

The head does not move; it rewrites the symbol as itself.

\(M_3\)	\(\triangleright\)	\(a\)	\(\square\)
\(q_0\)	\((q_0, \rightarrow)\)	\((q_0, \leftarrow)\)	\((q_0, \leftarrow)\)

The head oscillates between the end marker and the first character.

One state each

Non-termination is not the preserve of complicated programs.

Undecidability is not caused by complexity.

SIMULATE is semidecidable

\[L = \{\langle M, w \rangle \mid \text{TM } M \text{ accepts input string } w\}\]

SIMULATE(<M, w>)
1. Simulate TM M on input string w
2. if M accepts w then
3.     accept
4. elseif M rejects w then
5.     reject

If \(M\) runs forever on \(w\), SIMULATE runs forever. Exactly like \(U\) last unit.

Now assume it always halts

PARADOX(<M>)
1. result <- SIMULATE(<M, <M>>)
2. if result = accept then reject
3. elseif result = reject then accept

Then invoke PARADOX(<PARADOX>).

The contradiction

Case 1. PARADOX accepts \(\langle\)PARADOX\(\rangle\)

\(\implies\) SIMULATE rejects \(\langle\)PARADOX\(, \langle\)PARADOX\(\rangle\rangle\) \(\implies\) PARADOX rejects \(\langle\)PARADOX\(\rangle\)

Case 2. PARADOX rejects \(\langle\)PARADOX\(\rangle\)

\(\implies\) SIMULATE accepts \(\langle\)PARADOX\(, \langle\)PARADOX\(\rangle\rangle\) \(\implies\) PARADOX accepts \(\langle\)PARADOX\(\rangle\)

SIMULATE is algorithmically impossible.

The same shape, for HALT

\[L = \{\langle M, w \rangle \mid \text{TM } M \text{ halts on input string } w\}\]

PARADOX(<M>)
1. result <- HALT(<M, <M>>)
2. if result = accept then run forever
3. elseif result = reject then accept

Case 1. accepts \(\implies\) HALT rejects \(\implies\) runs forever.

Case 2. runs forever \(\implies\) HALT accepts \(\implies\) accepts.

Both constructions, side by side

Built on SIMULATE.

Built on HALT.

Only the middle box and one output label change.

What this rules out

No perfect infinite-loop detector.

No perfect static analyser for arbitrary runtime behaviour.

Ever, in any language.

Two ingredients made it work, both from the previous unit: programs encode as data, and a machine can be handed its own encoding.

Reductions spread unsolvability

Diagonalization once, then reduce

\[L_{\text{old}} \leq_m L_{\text{new}}\]

if there is a computable \(f\) with

\[x \in L_{\text{old}} \iff f(x) \in L_{\text{new}}\]

The picture

Yes-instances land in \(L_{\text{new}}\); no-instances land in its complement.

The \(m\) stands for many-to-one.

The consequences

If \(L_{\text{old}} \leq_m L_{\text{new}}\):

• if \(L_{\text{old}}\) is undecidable, so is \(L_{\text{new}}\)
• if \(L_{\text{old}}\) is not semidecidable, neither is \(L_{\text{new}}\)
• if \(L_{\text{new}}\) is decidable, so is \(L_{\text{old}}\)

HALT again, by reduction

Assume HALT is algorithmically possible. Then build:

SIMULATE(<M, w>)
1. result <- HALT(<M, w>)
2. if result = reject then reject
3. elseif result = accept then
4.     Simulate M on w
5.     if M accepts w then accept
6.     elseif M rejects w then reject

Line 2 is what makes it terminate.

Therefore

If HALT is an algorithm, so is SIMULATE.

But SIMULATE is impossible.

So HALT is impossible.

Direction is everything

We reduce the known-hard problem to the new problem.

The reverse proves nothing — it says the new problem is no harder than something impossible.

To check yourself: write out the imagined decider and see which problem it decides.

This is the most common error in the topic. Every year.

Which questions about machines are solvable?

Algorithmically solvable

• Does \(M\) have at least 481 states?
• Does \(M\) take more than 481 steps on input \(\epsilon\)?
• Does \(M\) take more than 481 steps on some input?
• Does \(M\) take more than 481 steps on all inputs?
• Does \(M\) ever move its head more than 481 cells from the left endmarker on \(\epsilon\)?

They all share a bound.

Why a bound decides it

“More than 481 steps on \(\epsilon\)?”

Simulate for 482 steps and look.

That simulation always halts — the step count is fixed in advance.

Algorithmically unsolvable

• Given \(M\) and \(w\), is \(w \in L(M)\)?
• Is \(L(M)\) nonempty?
• Is \(L(M) = \Sigma^*\)?
• Is \(L(M_1) = L(M_2)\)?
• Is \(L(M_1) \subseteq L(M_2)\)?
• Is \(L(M_1) \cap L(M_2)\) nonempty?
• Given \(M\) and \(w\), does \(M\) use a finite amount of tape?

They all quantify over all inputs.

The move to practise

Given a new question, ask: could a finite amount of simulation settle it?

• Yes → probably decidable. Say how much simulation.
• No → look for the reduction. Remember the direction.

The pattern

Anything a finite check settles is decidable.

Anything requiring behaviour on all inputs generally is not.

Summary

Four techniques, in order

• Counting proves unsolvable problems exist without naming one.
• Diagonalization names one.
• Self-reference reaches the problem people care about.
• Reduction turns one result into unlimited results.

Reduction is the one you will actually use.

What you can now do

• Define an algorithm as a machine that halts on every input.
• Place a problem as decidable, semidecidable, or neither.
• State the Church-Turing thesis and say why it is a hypothesis.
• Prove by counting that most problems are not semidecidable.
• Construct \(L_d\) and derive the contradiction.
• Prove SIMULATE and HALT impossible by self-reference.
• Write a reduction in the correct direction.
• Sort questions about machines as bounded or behavioural.

The limit is not the machine’s

The previous unit built a model of computation and found it strong enough to do anything a computer can.

This unit found its edge.

By the Church-Turing thesis, that edge is the limit of computation — no faster hardware and no better language moves it.

What real tools do about it

Every question about arbitrary program behaviour is undecidable in general.

Real tools work because they give up something:

• they approximate
• they restrict the language
• they answer “don’t know”

Knowing which of the three a tool has chosen is the useful form of everything proved here.