The Halting Problem – there is, definitively, more to thinking than computation

Alan Turing

Alan Turing

Kurt Gödel’s Incompleteness Theorem[1] was inspired by David Hilbert’s question “Are the axioms of a formal system sufficient to derive every statement that is true in all models of the system?” Hilbert played the same role regarding Alan Turing’s proof of the halting problem. Hilbert had asked: “Is there some mechanical procedure [an algorithm] for answering all mathematical problems, belonging to some broad, but well-defined class?”[2] In German this is called Entscheidungsproblem – the decision problem.[3]

Turing found that he could answer this question by framing it in terms of a Turing machine[4] – could there be a program that could determine whether any other arbitrary computer program and input would eventually stop or just loop forever? This was called the halting problem.

“Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.”[5]

Continue reading

LaPlace iff Plato

Naturalistic explanations can work as descriptions of actual causal relations among reals only if nominalism is false, so that their terms – mass, extension, momentum, 2, h, valence, π, spin, c, equilibrium, homeostasis, system, organism, state, fitness, and so forth – truly refer. Otherwise, they are nothing but vain wind.

But the falsity of nominalism entails the reality of the Forms. It entails supernaturalism.

Continue reading