A Structural Explanation of the Undecidability of the Halting Problem in Turing Machines

bz's Substack

SubscribeSign in

A Structural Explanation of the Undecidability of the Halting Problem in Turing Machines<br>Beyond the Paradox: What Structural Limits Make a Computation Model Decidable?

bz<br>Aug 17, 2026

Share

Introduction

In his seminal 1936 paper, Alan Turing introduced the concept of the Turing machine and proved a definitive result: there is no general algorithm that can determine whether an arbitrary Turing machine will halt on a given input. This is the famous Halting Problem .<br>This result is typically explained as an instance of a self-referential paradox, akin to the Barber Paradox or Russell’s Paradox. But why does the Turing machine, as a computational model, natively support self-reference? If we wanted to construct a “safe” computational system—one that guarantees a solution to the decision problem—what capabilities would we need to restrict?<br>Thanks for reading bz's Substack! Subscribe for free to receive new posts and support my work.

Subscribe

This article seeks to offer an intuitive yet mathematically grounded explanation based on the structural characteristics of the Turing machine.<br>1. The Four Foundational Dimensions of a Turing Machine

We can decompose the computational power of a Turing machine into four mutually orthogonal dimensions:

Among these, the State Access Pattern is the most critical—and most frequently overlooked—dimension.<br>1.1 Destructiveness

Destructiveness refers to whether accessing a state leaves that state, as well as all other states in the system, unchanged.<br>Destructive Access: Accessing a state alters or consumes it. Reading requires destroying the current state or other surrounding structures. An example is a single-pass input iterator: once the current character is read, the pointer advances, and the previous position can never be accessed again.

Non-destructive Access: Accessing a state leaves all states intact, allowing multiple reads. The Turing machine’s tape functions this way: when the read/write head moves to a cell and reads a symbol, the symbol remains unchanged.

1.2 Retrospectivity

Retrospectivity refers to the ability to access past states while maintaining non-destructiveness.<br>Non-retrospective: Historical states cannot be read without destroying other structural data. Consider a stack: although historical data is stored inside it, accessing deeper layers requires popping top elements—destroying non-destructiveness. The popped data is lost permanently.

Retrospective: Arbitrary historical states can be accessed non-destructively without altering any state. The Turing machine tape embodies this capability: all historical data persists on the tape, and the head can rewind to any arbitrary cell at any time.

(Note: Pairing two stacks restores retrospectivity. Data can be moved to an auxiliary stack during retrospective access and popped back to restore the original state upon completion.)<br>Combining these two dimensions yields four configurations:<br>Access PatternStructural MeaningDestructive / Non-retrospective Forward-only iterator. Consumed upon reading; no going back.Non-destructive / Non-retrospective Stack. Reading the top element is non-destructive, but bottom elements cannot be read non-destructively.Destructive / Retrospective Invalid combination; “retrospectivity” requires non-destructiveness by definition.Non-destructive / Retrospective Random-access memory. Any location can be read non-destructively and revisited arbitrarily.<br>2. Why the Universal Decision Problem Is Undecidable

Turing’s proof relies on proof by contradiction. The pivotal step involves feeding a program its own source code as input—a construction known as self-reference . Let us examine what self-reference requires and how it is constructed.<br>2.1 What Does Self-Reference Require?

Formally, constructing a self-referential program $P$ is simple:<br>Program $P$: Read your own complete source code $S$. Then, use $S$ to perform an action (e.g., pass $S$ to a halting decider $H$, ask “Do I halt?”, and then execute the opposite behavior).

How does a program read its complete self?<br>This is not a philosophical question, but a concrete structural prerequisite. At runtime, program $P$‘s source code exists as a data object—a principle fundamental to Universal Turing Machines, which encode machine instructions as data on the tape.<br>Turing’s diagonal argument centers on the call $H(P, P)$, where the same instance $P$ is passed as two distinct arguments. This imposes three structural requirements on the underlying model:<br>The system must be able to access the exact same data object $P$ multiple times.

Between accesses, $P$ must remain unchanged, requiring non-destructive access.

$P$ is a complete description of the program, including its “past self,” requiring the system to look back at previous states—i.e., retrospective access.

The tape access mechanics of a Turing machine satisfy...