Turing Machines and Computable Functions

Motivation: What is an "algorithm"?

Until the 1930s, the notion of "algorithm" was intuitive. In 1936, Turing proposed a mathematical model of computation—a Turing machine (TM)—and substantiated the thesis: anything that a person can compute "mechanically" is computed by a TM. This made it possible to rigorously prove the existence of uncomputable functions.

Formal Definition of Turing Machine

Deterministic TM M = (Q, Σ, Γ, δ, q₀, q_acc, q_rej):

• Q — a finite set of states.
• Σ ⊆ Γ — input alphabet (□ ∉ Σ, □ is the blank symbol).
• Γ — tape alphabet.
• δ: Q × Γ → Q × Γ × {L, R} — transition function (read, write, move the head).
• q₀ — initial state; q_acc, q_rej — accepting and rejecting.

Configuration: (q, u, a, v) — state q, tape = u·a·v, head over a. Compact notation: u_q_v (underlines the position of the head).

Acceptance: M accepts w if computation from the initial configuration reaches q_acc. Rejects if it reaches q_rej. Loops if it reaches neither.

Decider: TM which halts on any input (accept or reject). If L is accepted by a decider, L is decidable. If L is recognized only by a TM, L is enumerable (RE, recursively enumerable).

Church–Turing Thesis

Thesis: A function is computable "in the intuitive sense" ⟺ it is computable by a Turing machine.

This is a thesis (philosophical principle), not a mathematical theorem: it is impossible to formally prove that the intuitive notion matches the TM. Indirect confirmation—coincidence of TM with λ-calculus (Church), primitive recursive functions + minimization (Gödel–Herbrand–Kleene), RAM-machines.

Partially recursive functions: closed under composition, primitive recursion, and μ-minimization. Coincide with those computable by a TM.

Languages and Hierarchy

• Decidable ⊊ RE (enumerable) ⊊ All languages.
• co-RE = {L : L̄ ∈ RE}. L is decidable ⟺ L ∈ RE ∩ co-RE.

Numerical Example

Task: Describe the operation of a TM recognizing palindromes over {a, b}.

Step 1. Idea: read the first symbol, remember it in the state (state encodes "first symbol = a" or "= b"), move to the end, check if the last symbol matches, erase both, repeat.

Step 2. States Q = {q₀, qₐ, q_b, q_seek_a, q_seek_b, q_return, q_acc, q_rej}.

Step 3. Trace for w = "aba":

• Start: _q₀_aba. Read 'a', remember it (transition to qₐ), erase the first symbol (→ □): □qₐ_ba. Move right to the end: □b_qₐ_a. Read last 'a': matches qₐ → erase: □b_q_ret□.
• Return left: q_ret□b□. Find next symbol 'b', transition to q_b, go right: □_q_seek_b_b□. Last 'b' matches: □q_ret□□□. Tape is empty → accept ✓.

Step 4. For w = "ab":

• Read 'a' → qₐ: □_qₐ_b. Last symbol 'b' ≠ 'a' → reject ✓.

Formally, this TM has O(1) states and operates in O(n²) steps (each pass—O(n), n/2 passes).

Real Application

Compilers: syntactic analysis checks if the program is a "word" in the grammar's language. Chomsky grammars correspond to levels of TM hierarchy. Regular expressions—finite automata; parsing JSON—context-free grammars; a full programming language—a decidable TM.

Additional Aspects

Computability theory studies which functions can, in principle, be computed by any formal algorithm. The Church–Turing thesis asserts the equivalence of all reasonable models: Turing machines, λ-calculus, recursive functions, register machines, cellular automata (Conway’s Game of Life is Turing complete). From the undecidability of the Halting Problem follows the undecidability of checking program equivalence, coverage of execution paths, verification of arbitrary programs. Nevertheless, in practice static analyzers (Coverity, Infer, MIRAI) use approximating algorithms—they give a finite answer in acceptable time, sacrificing either completeness (may miss an error) or correctness (may raise a false alarm).

Connection with Other Areas of Mathematics

The concept of computability naturally relates to the theory of differential equations through results by Peter Pour-El and Jörg Richards on the existence of well-posed problems for the heat equation and wave equation, whose solutions at certain points turn out uncomputable given computable initial data. This illustrates that even classical problems of analysis may conceal an "embedded" effect of the universal Turing machine.

In algebra, a key bridge is the word problem in groups. The works of Novikov and Boone (1940s) showed the existence of finitely presented groups with an unsolvable word problem; the construction relies on encoding Turing machine configurations in group relations. Later, Adyan and Rabinovich developed these ideas, linking recursively enumerable sets to normal forms of words.

In topology, the well-known result of Mark Davis and coauthors is the undecidability of recognizing sphericality of 3-manifolds: there exists algorithmically undecidable determination whether a given compact 3-manifold is a topological 3-sphere. The constructions also use simulation of Turing machines at the level of fundamental groups and triangulations.

Probability theory intersects with computability via algorithmic information theory. Kolmogorov, Levin, and Chaitin define the randomness of a sequence via the nonexistence of a short program on a universal Turing machine that generates its initial segments. This leads to the uncomputable Chaitin constant, related to the probability of halting for a universal machine.

Numerical methods and computational mathematics use Turing machines as a reference for analyzing complexity. The classic works of Traister, Kohrst and Traub investigate which problems of numerical integration or solving nonlinear equations can be solved in polynomial time on the Turing model, introducing the concept of information complexity and linking continuous problems with discrete complexity theory.

Historical Note and Development of the Idea

The idea of formalizing the algorithm emerged in parallel in several traditions. In 1936, Alan Turing published in the Proceedings of the London Mathematical Society the article "On Computable Numbers, with an Application to the Entscheidungsproblem," where he introduced the abstract machine and proved the unsolvability of the problem of general validity for first-order formulas. Independently, Alonzo Church in 1936 in the American Journal of Mathematics used λ-calculus and the notion of effective computability to prove the same limits of formal systems. Kurt Gödel, in his 1934 lectures in Princeton, discussed primitive recursive functions, and Gödel, Herbrand, and Kleene (1930s) added the minimization operator, creating an alternative definition of partially recursive functions equivalent to Turing's. Emil Post proposed his production model (Post systems) and formulated the Post problem of equilibrium, later shown equivalent to undecidability. In the second half of the 20th century, the theory developed towards the classification of unsolvable problems and hierarchies by complexity degree.