In modern logic and computation theory, “computability” and “decidability” are two core concepts. However, these notions not only concern the internal limits of formal systems—they also reflect two fundamental modes of human thought: deductive reasoning and inductive intuition. This cognitive structure was formally expressed in Turing’s two seminal papers.
Let’s first consider computable problems. These correspond to human deductive reasoning—starting from established axioms, proceeding through a series of strict, repeatable steps to reach a definite conclusion.
In formal computational models, this process was delineated by Turing in 1936 as the problem of “computable numbers.” In his groundbreaking paper “On Computable Numbers, with an Application to the Entscheidungsproblem”, he defined the Turing Machine model.
A Turing Machine is a deterministic computational system: it follows fixed state-transition rules to process input and produce output. Every step is a deductive result—just like how humans proceed step-by-step from premises to conclusions in logical reasoning.
This means:
But human thought goes far beyond deduction.
In everyday life, we often guess, make analogies, or act on intuition. This capacity is difficult to simulate with a Turing Machine. Thus, in his 1938 doctoral dissertation “Systems of Logic Based on Ordinals”, Turing proposed a revolutionary model: the Oracle Turing Machine.
The core of the Oracle Machine is this: it has access to an external information source—an oracle—which can provide direct answers at critical decision points.
This model corresponds to non-deductive cognitive behaviors such as induction, analogy, guessing, and intuitive judgment.
Thus:
These problems are not solvable by a standard Turing Machine, but can be solved given some additional knowledge (akin to a priori cognition), embodying the idea of relative computability.
This correspondence is no coincidence—it profoundly reveals the dual-track mechanism of human cognition:
When we shift from “formal systems” to “cognitive models,” we see that Turing already laid this path in the 1930s.
Turing’s two papers—one from 1936 on computable numbers, and the other from 1938 on ordinal logic systems—form the twin pillars of modern computational theory.
They not only underpin the theoretical foundation of AI and complex systems but also reflect a mirror of human cognition:
Why can we both reason deductively and judge intuitively?
This is not just a question of computation—It’s a question of philosophy and human intelligence.
