— Between First-Order and Second-Order, Witnessing the Limits and Leaps of Computation

In the history of human thought, the development of logic resembles climbing a staircase of abstract cognition. Starting from propositional logic, we gradually moved toward predicate logic with stronger expressive power. This path not only reshaped the foundations of mathematics but also gave birth to modern computational theory. Alan Turing’s intellectual trajectory marks two key steps on this ladder:

✅ First-Order Predicate Logic

✅ Second-Order Predicate Logic

➕ The profound boundary of expressiveness and computability between them

I. From Sentences to Structures: The Refined Language of Predicate Logic

In propositional logic, we treat the entire sentence as an “atom.” For example, “Pat loves Terry” is an indivisible logical unit.

But predicate logic changes everything:

Loves(Pat, Terry) structures the sentence as “relation + individuals”

It can express complex relationships and attributes between objects, enabling more refined and analyzable reasoning, and is closer to the structure of natural language. More importantly, predicate logic introduces the core tool of Quantifiers. We can express:

∀x Loves(x, Pat): Everyone loves Pat

∃x Loves(x, Pat): Someone loves Pat

The emergence of quantifiers is a leap from “judgment” to “induction and universality” in logical language.

II. First-Order vs. Second-Order: The Boundary and Cost of Expressiveness

What can quantifiers apply to? The answer to this question determines the hierarchy and capabilities of logical systems.

🧩 First-Order Predicate Logic (FOL)

Quantifiers apply only to “individual variables”

Example: ∀x (Apple(x) → Red(x))

It possesses completeness and decidability and serves as the foundation of modern mathematics and computation.

🌌 Second-Order Predicate Logic (SOL)

Quantifiers can apply to “properties,” “relations,” “sets,” and other higher-order objects

Example:

∀x ∀y (Hero(x) ∧ Hero(y) → ∃P (Thinks(x, P) ∧ Thinks(y, P)))

This expresses: “Any two heroes share some common belief P.”

It has immense expressive power, capable of defining mathematical induction, set axioms, and more, but at a cost: undecidability, inexhaustibility, and incompleteness. First-order logic is a tamed language; second-order logic is a tool for expressing infinite complexity.

III. Turing’s Leap: Using Higher-Order Thinking to Tackle First-Order Problems

In 1936, Turing constructed the Turing Machine model in his paper On Computable Numbers, defining computability and proving the undecidability of the “decision problem” within first-order logic. Yet by 1939, in his PhD thesis Systems of Logic Based on Ordinals, he proposed a more radical idea:

Form: (∀x)(∃y) R(x, y)

where R is a recursively computable relation.

Syntactically, this still belongs to first-order logic, but its truth evaluation surpasses the capacity of a Turing Machine, belonging to the second level (Σ₂) of the arithmetical hierarchy. To address this, Turing introduced two key concepts:

🔸 Ordinal Logic

By “induction to higher ordinals,” attempting to build a sequence of increasingly powerful logical systems.

🔸 Oracle Machine

A hyper-Turing machine that can accept external “decision” instructions.

The core idea of these constructs is: when faced with undecidable propositions, higher-order judgment systems enable iterative leaps.

IV. Epilogue: A Distant View from Logic to the Philosophy of Computation

Logic is the language through which we understand the world. Computational theory sets the boundaries and possibilities within that language.

First-order logic: precise and controllable—the “light of reason” in formal systems.

Second-order logic: immensely expressive but incomplete—a tool for portraying the complexity of the world.

Turing’s contribution: built a bridge between computability and undecidability, demonstrating the fusion of rationality and intuition.

✅ The boundary of computability lies not in syntax, but in the architecture of cognition itself.

✅ Turing’s Oracle Machine is an abstract model of intuitive judgment within logical systems.

✅ When a system cannot judge itself, higher-order structures must be introduced.

From predicates to quantifiers, from first-order to higher-order, from Turing Machines to Oracle Machines—this is a staircase of thought paved by language, computation, and cognition. And Turing himself is the intellectual engineer who built the bridge between reason and the infinite.