Computable and Non-Computable Functions

In 1936, Turing proved something deeply uncomfortable. There exist problems that are algorithmically impossible to solve - not due to lack of computing power, but as a matter of mathematical law. ChatGPT cannot determine whether an arbitrary program will halt. No LLM ever will. Your IDE cannot guarantee the absence of infinite loops. The Rust borrow checker rejects some valid programs on purpose - because precise analysis is undecidable. This is not a gap in engineering. It is a proven mathematical barrier, established before the first computer was ever built.

• **Static analysis tools:** VS Code, IntelliJ, Pylance are all conservative by design - they miss real bugs because precise analysis of arbitrary code is undecidable. This is the mathematical ceiling, not an engineering shortcut
• **Antivirus software:** VirusTotal, Windows Defender, and every other scanner rely on signatures and heuristics - a universal detector of arbitrary malicious code cannot exist. Rice's theorem forbids it
• **Formal verification:** Amazon uses TLA+, AWS S3 is verified with Coq - but only for finite, explicitly described systems. Verifying an arbitrary program is impossible in principle

Computable Functions

**A calculator adds two numbers. Always.** For any inputs, in finite steps, with the same result every time. Addition is **computable**: an algorithm exists that guarantees an answer. That sounds unremarkable - until one asks which functions are not computable, and why.

A **computable function** is a function f: N → N for which there exists an algorithm (a program, a Turing machine) capable of computing f(x) for any input x in a finite number of steps.

The key word is **algorithm** - a precise sequence of steps that can be written in any programming language. Python, Haskell, assembly - it does not matter. By the Church-Turing thesis, all sufficiently powerful languages compute exactly the same class of functions.

The consequence: if a problem cannot be solved in Python, it cannot be solved anywhere. Not in another language, not on a quantum computer, not on anything that could be built in the future. Computability limits are **mathematical**, not technological - the single most important distinction in theoretical computer science.

Total Functions

Not all functions are equally dependable. A **total function** is defined for every input - it always terminates, always gives an answer. In real-time systems (RTOS, aviation software, medical devices) only total functions are acceptable: hanging is equivalent to failure.

A **total computable function** is a computable function f that is defined for **all** natural numbers. The program computing f terminates on every input.

The **Collatz problem** is an example on the boundary: we **believe** the function is total (i.e., always reaches 1), but this has not been proved mathematically. For some n the program might run forever - we simply do not know.

Here is the first non-trivial fact: it is **impossible to write a program** that reliably determines, for any other program, whether it is total. This is why TypeScript cannot verify all invariants, and why the Rust compiler rejects some correct programs - precise totality checking is undecidable.

Partial Functions

**A program has been running for an hour.** Started overnight, still going in the morning. Stuck forever, or about to finish? If a program gives no answer on some inputs, it computes a **partial function**. Most real programs are partial: interpreters, servers, search algorithms.

A **partial computable function** is a function for which an algorithm exists but the algorithm may not terminate on some inputs. The function is "defined" only where the algorithm halts.

The fundamental **asymmetry**: if the program produced an answer, the result is certain. But if it is still running, there is no way to tell whether it is stuck or computing. This is not a debugging problem. It is a fundamental fact about computation.

Programs can be enumerated - they form a **countable** set (like the natural numbers). Functions N → N are **uncountable** (like the reals). The gap between these cardinalities is absolute. The overwhelming majority of mathematical functions are not merely unsolved - they are provably beyond the reach of any algorithm.

Non-Computability and the Halting Problem

Turing was 23. The computer had not been built yet. And he proved that **there exist problems no computer will ever solve** - not for lack of power, but because a solution leads to a logical contradiction. The proof fits in 20 lines of code and hinges on one elegant trick.

The **Halting Problem**: given a program P and an input x, determine whether P(x) terminates in finite time or runs forever. Alan Turing proved in 1936 that this problem is **undecidable** - there exists no algorithm that solves it for all pairs (P, x).

The proof is an elegant **diagonalization** argument (by contradiction). Suppose such an algorithm HALTS(P, x) exists. We build a paradox on top of it:

The consequences are immediate and concrete. An IDE cannot reliably catch all infinite loops. A compiler cannot guarantee the absence of deadlocks in arbitrary code. A static analyzer misses bugs - not from lack of effort, but because precise analysis reduces to the halting problem. Rice's theorem (1953) formalizes this: any non-trivial behavioral property of an arbitrary program is undecidable.

The deeper point: computability is the exception, not the rule. Programs are countable; functions N → N are uncountable - the same gap as between the naturals and the reals. All algorithms, languages, and architectures ever devised are a tiny island in an ocean of non-computability. Turing charted the boundary of that island before the first computer existed.

Key Ideas

• **Computability is not about hardware:** if a problem is undecidable for a Turing machine, no quantum computer, no AGI, no future supercomputer will solve it either - it is a mathematical barrier, not an engineering one
• **Total vs partial:** a total function guarantees an answer on every input; a partial one may loop - and no algorithm can reliably tell the difference for an arbitrary program
• **The halting problem anchors everything:** Turing's diagonalization proof is the template for hundreds of undecidability proofs. Program equivalence, bug detection, totality checking - all reduce to it
• **Non-computability is the norm:** programs are countable, functions N → N are uncountable. Almost every mathematical object is beyond algorithmic reach - we simply never encounter those objects in practice

Related Topics

Computability is the foundation on which all of theoretical computer science is built:

• Turing Machine — The formal model through which computability is defined
• Recursive and RE Languages — Classification of languages by computability - the next level of theory
• Formal Languages — The connection between grammars, automata, and computability

Вопросы для размышления

• If the halting problem were decidable - what programming tools would become possible?
• Why does the impossibility of creating a "universal debugger" not prevent us from creating useful (but imperfect) code analysis tools?
• How is the argument about the countability of programs and the uncountability of functions related to Cantor's diagonal argument about real numbers?

Связанные уроки

• fl-01-intro — Recursively enumerable languages (type 0) are exactly those recognized by Turing machines
• cplx-01 — Computability is a prerequisite for complexity theory: first can-it-be-solved, then how-fast
• aut-01-fsm — Turing machine = finite automaton + infinite tape; formally more powerful model
• dm-01 — Cantor's diagonalization and the Halting Problem proof use the same self-reference technique
• fl-18-turing-machine