Bob's Blog

The Recurring Delusion of Hypercomputation

Both mathematical theory and computation theory are limited. There will always be arithmetic problems that cannot be solved by mathematics, and decisions that cannot be made by formal logic methods. All of that was proved in the 1930s. These aren't fringe claims that are about to be disproved. A decent computer science program will put you through a course in which you work through the proofs. Everyone studies this and no one has spotted a weakness.

Kurt Gödel published two theorems in 1931, known as his Incompleteness Theorems. They show that mathematics is inherently limited. There can be no consistent system of axioms that can prove all truths about the arithmetic of the natural numbers, the non-negative integers. There will always be statements about natural numbers that are true, but cannot be proved to be true within that system. There also will always be statements about natural numbers that are false, but cannot be proved to be false within that system.

Mathematics is limited. Mathematics can always pose a question that it cannot answer.

In 1935–1936, Alonzo Church and Alan Turing worked to apply Gödel's proof of the incompleteness of mathematics to formal logic and problem solving. This was an early major development in what would, decades later, be called computer science. David Hilbert had posed a "decision problem", Entscheidungsproblem in German, in 1928. Church published his paper "An Unsolvable Problem of Elementary Number Theory" in April 1936, and the following month Turing finished his broader paper "On Computable Numbers, with an Application to the Entscheidungsproblem". In it he first described a theoretical "universal computing machine", what everyone now calls a Turing machine. He then showed that the decision problem had no solution because the halting problem has no solution.

Computational theory is limited. There will always be problems posed within a formal logic system that an arbitrarily large computing system cannot solve.

It's now 2025, we have known of the unsurmountable limitations of mathematics and computer science for 94 and 89 years, respectively.

That does not keep promoters of AI hype from claiming that they're on the verge of doing the impossible, if only they could have a little more funding and other resources.

Kurt Gödel, around 1926.

Alan Turning, in 1951.

What Would "Hypercomputation" Be?

Alan Turing's 1938 Ph.D. thesis Systems of Logic Based on Ordinals he proposed an oracle, a mathematical abstraction that would be more powerful than the universal computing machines described in his 1936 paper. Turing's oracle is an abstraction that could not be physically realized. But that doesn't matter, because he then proved that even such an impossible device still could not solve the halting problem or Hilbert's decision problem.

Several models of hypercomputers have been proposed. Some start by requiring that the physical laws of our universe work differently.

Others would require an infinite number of computational steps, meaning that they would never produce an answer no matter how long you waited. Enthusiasts of time travel suggest that one of their non-existent time machines might let an infinite-time program finish, but it's been proven that even that wouldn't help.

There is excited hand-waving about how a quantum mechanical system with an infinite superposition of states could do the job. But the actual quantum computing devices we know of wouldn't do that.

It's a lot of: "If only everything were different, then we could do this!"

Why Does This Pointless Quest Keep Recurring?

Because influential people keep wanting to do impossible things that would be to their great personal benefit, if only those things somehow became possible in our universe.

The ultra-wealthy oligarchs want to have their heads removed and frozen shortly before death, cryogenically preserved until some future technology can convert the freezer-burned mush back into healthy tissue and recover and restart their conciousness. The usual shouted hand-waving claim is that nanobots, tiny medical robots smaller than blood cells, will do the work.

Look, nanotechnology is certainly a thriving science. We can build semiconductor circuitry, electro-optical devices, and materials at the nanometer scale. But that in no way means that it would be practical to pack the required wide range of sensors, manipulators, and the computational power needed for the sensory analysis, planning, and manipulation into a device smaller than a cell and capable of re-creating and manipulating cellular organelles. The oligarchs keep shouting "BUT THE NANOBOTS WILL BECOME AVAILABLE, EVENTUALLY!"

Other oligarchs are more interested in somehow transferring their consciousness into a computer, so they can live on forever as a running process on some God-like computing platform. But philosophers, neurologists, and logicians are all unable to explain what consciousness is or how to verify that another human has it.

The oligarchs shout "THE A.I. WILL FIGURE IT OUT, IF WE BUILD ENOUGH DATA CENTERS!"

There is no "Turing Barrier" to Break

There is a lot of wishful magical thinking. AI hype promoters spin their stories around assumptions that the provably impossible will become available. Some talk of breaking through "the Turing Barrier". But there is no such breakable barrier to break through.

If a decision is incomputable as described in the Church-Turing thesis, then no algorithm running within a consistent formal logical system cannot solve it. A bigger supercomputer cannot solve it. Nor would it help to add a few more data centers full of computers. Nor would it help to wait even longer for the algorithm to finish. Incomputable decisions cannot be computed.

Proponents of hypercomputation have to rely on inappropriate assumptions and circular arguments. If only the laws of physics worked differently, or if only formal logic would logically violate itself, or...

Paolo Cotogno wrote a readable 14-page critique of hypercomputation. Martin Davis wrote a far more amusing 4-page beat-down of the nonsense.