← CSC 313 Theory of Computation
Turing Machines, Decidability, and the Halting Problem
Notes
The Turing Machine Model
The Turing Machine, proposed by Alan Turing, represents the mathematical gold standard for universal computation. Unlike finite automata or pushdown automata, a Turing machine features an unbounded, bidirectional tape that serves as both working memory and input storage. A read-write head navigates this tape, moving one cell left or right per computational step while rewriting symbols. The machine is defined by states, a tape alphabet, an input alphabet, transition functions, and designated accept and reject states. If an algorithm can be implemented on any modern physical supercomputer, the Church-Turing thesis asserts it can also be evaluated by a Turing machine.
Decidability and Undecidability
A language is deemed decidable or recursive if there exists a Turing machine that halts on every possible input string, either accepting or rejecting it definitively. If a machine loops infinitely on some inputs without ever halting, the language is at best Turing-recognizable (recursively enumerable), but not decidable. Decidability represents the boundary of problems that can be solved algorithmically within finite time guarantees.
The Halting Problem
The Halting Problem asks whether an algorithm exists that can take any arbitrary program description and an input, and correctly determine whether the program will eventually halt or execute forever. Turing proved via proof by diagonalization that the Halting Problem is strictly undecidable. No universal debugger can ever be engineered that accurately flags infinite execution across all conceivable software programs.
Practical example
Consider the Central Bank of Kenya (CBK) operating the Kenya Real-Time East African Payment System (KEPSS), which facilitates high-value interbank settlements across commercial institutions such as KCB, Equity Bank, and NCBA. The clearing house allows commercial banks to submit custom batch-processing scripts that calculate complex liquidity balancing algorithms during end-of-day clearing.
A junior systems engineer at CBK suggests developing a static analysis safety filter that inspects every bank settlement program before execution to guarantee with absolute certainty that no submitted script will enter an infinite loop and freeze the national clearing settlement cycle.
Applying Theory of Computation concepts, senior computer scientists demonstrate that such a universal verification tool is computationally impossible. Because settlement scripts are Turing-complete programs capable of arbitrary branching and dynamic state manipulation, constructing a program that decides whether every arbitrary script halts on a given ledger balance is identical to solving the classical Halting Problem. Instead of seeking an impossible theoretical verifier, CBK engineers must enforce pragmatic operational bounds, such as hard execution timeouts and gas limits, guaranteeing that runaway interbank settlement scripts are forcefully terminated.
Quiz
1. Which hardware capability fundamentally grants Turing machines greater computational power than Pushdown Automata?
2. How must system architects at institutions like the Central Bank of Kenya handle undecidable software looping risks?
3. What does Alan Turing's resolution of the Halting Problem formally establish?
Sign in to submit and securely grade your quiz.