What can a computer really do? And above all: what will it never be able to do, however powerful it becomes? The answer is not an opinion for a television debate: it is a theorem, proved in 1936 by a twenty-four-year-old mathematician who was inventing the machines at that very moment. In the chapter «The Machine and the Limit» of Beyond Turing - The Incalculable Remainder, Antonio Fabbrizio reconstructs the mathematical foundation of the entire edifice of computing - and of its boundary - with a rigour that speaks directly to those who practise engineering.
The starting point is Hilbert's decision problem, the Entscheidungsproblem: does there exist a mechanical procedure capable of establishing, for any mathematical statement, whether it is provable? To answer, Alan Turing first had to define what it means to compute: thus was born the machine that bears his name - a tape, a head, a finite set of states and rules - and with it the universal machine, capable of simulating any other. That universal machine we now carry in our pockets: smartphones, hospital servers, enterprise information systems, the platforms that train large language models are, in their mathematical essence, the same 1936 machine made faster.
The halting problem and Rice's theorem
But an exact definition has exact boundaries. Turing proved that there exist perfectly defined problems that no machine will ever solve: the most celebrated is the halting problem - no algorithm can establish in advance, for any program and input, whether the program will terminate. Not «not yet found»: it cannot exist, with the same necessity by which there is no largest prime number. Rice's theorem (1953) generalizes the blow: every non-trivial property of program behaviour is undecidable. And Cantor's counting delivers the most vertiginous image of the chapter: possible programs are a countable infinity, possible problems are not.
«The computable functions are a countable island in an uncountable ocean.»- Beyond Turing, ch. 2, The Machine and the Limit
For those who design and certify systems, the practical consequence is enormous and highly topical: an algorithm that certifies in general the correctness of another program does not exist and never will. Human oversight of automated systems - the one prescribed by Article 14 of the AI Act - is not merely legal prudence: it is what remains necessary when mathematics itself proves that total automatic control is impossible. A 2024 regulatory obligation with a foundation that comes from 1936.
Gödel, the Turing test and language models
The chapter sets beside Turing the other giant of the boundary: Kurt Gödel, who in 1931 proved that every consistent formal system rich enough contains truths it cannot prove. Truth exceeding proof, decision exceeding the machine: two faces of the same boundary. And on the question everyone asks today - large language models passing the Turing test - the chapter's answer has a rare conceptual cleanliness: the test measures the indistinguishability of behaviour, not the existence of someone behind the behaviour. That conversation is largely computable has been demonstrated; that someone has appeared behind the surface has not. The error - already observed by Weizenbaum with ELIZA in 1966 - does not lie in the machine, which does what it is: it lies in the observer's inference, which deduces being from functioning.
Why «beyond» Turing
The title of the book finds its explanation in this chapter: «Beyond Turing» is not against Turing - it is, literally, what lies on the far side of the boundary Turing himself traced. The father of the universal machine is also the father of its first impossibility, and no one had a better claim to trace that boundary. Before the first computer was born, humanity already knew, with mathematical certainty, what no computer would ever be able to do. For the engineer building wonders on the island of the computable, it is the most solid methodological lesson there is: knowing the boundary does not diminish the craft - it founds it.
