Can AI Truly Reason? Part 2
Our Journey Exploring the Limits of Machine Intelligence, Computing Logic, and the Future of Hybrid AI Systems
Beyond Probabilism: Why AI Still Can’t Reason
In our previous exploration, we charted the rich philosophical history of reasoning—tracing its evolution from Plato’s ideal forms to the radical empiricism of Hume and the paradoxes tackled by Gödel, Tarski and many others.
We saw how human thinkers struggled with the tension between intuition and rigor, and how these age-old challenges resonate in modern attempts to build machines that can reason. Large language models, with their stochastic and prediction-driven nature, face fundamental limitations in domains requiring logical precision and formal consistency, like mathematics and philosophy.
In this article, we build on that foundation, diving deeper into the theoretical underpinnings that define the boundaries of computation. We explore the key ideas in computability theory, examining its core concepts such as Turing degrees, undecidable sets, and the limits of what can be computed. These concepts lay the groundwork for understanding where and why machines can fall short in the realm of formal reasoning.
We then pivot to the history and evolution of lambda calculus and combinatory logic—the foundational ideas that led to the development of functional computation. From Leibniz’s early dreams of a universal calculus of reason to the formalization of computation by Turing and Church, these theories have shaped how we approach computation today, influencing everything from modern programming languages to the development of artificial intelligence.
Together, these foundational concepts provide a crucial lens through which we can understand both the limitations and the potential of machines to reason. As we continue to explore the intersection of logic, learning, and computation, we gain insights that not only clarify the nature of formal reasoning but also inform the ongoing quest to build machines capable of more sophisticated, human-like thought.
The Fundamentals of Computation
But before we can truly understand the semantics of programming languages or how machines “reason”, we have to take a step back—into the very foundations of computation itself. Beneath every program, every abstraction, and every inference engine lies a core set of ideas that define what it even means to compute.
This is the realm of the broad theory of computation—a gigantic field that predates modern programming and still governs its formal limits. To talk about meaning, logic, or reasoning in programming, we must first ask:
What can be computed? What can’t be formalized? How? And where do the boundaries lie?
As you probably know, every AI system, every simulation, every interface we touch is shaped by the language in which it was written. These languages don’t just describe computations; they encode the very way we think about processes, systems, and logic.
And behind their surface lies a rich academic discipline known as programming language theory (PLT), a rigorous branch of mathematics, drawing heavily from set theory, category theory, and computability theory.
These mathematical foundations allow us to reason precisely about code: to prove whether programs terminate, to define equivalences between different language constructs, and to explore the limits of what can be computed. PLT is where syntax meets semantics, where logic meets structure—and it offers the formal scaffolding behind everything from compiler design to type systems to abstract interpretation.
Let’s dive deeper into those three underlying concepts and try to understand them in a comprehensive way.
Computability Theory
Let’s begin our journey by exploring Computability Theory, also known as recursion theory—a foundational branch of mathematical logic and theoretical computer science that examines the fundamental question:
What does it mean for a function to be computable? and Which problems are solvable by algorithms?
The field originated in the 1930s through the pioneering work of Kurt Gödel, Alan Turing, Alonzo Church, and others, who sought to formalize the intuitive notion of "effective procedures."
Key models that emerged from this huge effort include Turing machines, lambda calculus, and recursive functions—all of which were shown to be equivalent in computational power. This convergence led to the formulation of the Church–Turing thesis, which postulates that any function that is intuitively computable can be computed by a Turing machine, forming the philosophical and technical foundation of modern computation, with profound implications that are more relevant than ever in today’s world.
One of the most profound discoveries in computability theory is the existence of undecidable problems—problems for which no algorithm can exist. The classic example is the halting problem, which asks whether a given computer program will eventually stop or run forever. Turing proved that there is no general method to solve this for all possible programs, establishing a limit to algorithmic reasoning.
Beyond decidability, computability theory provides a rich framework for classifying problems based on their degree of noncomputability. This leads to the concept of Turing degrees, which group decision problems according to their relative computability. Problems with the same Turing degree are equally hard to solve (from a computability standpoint), while others may be strictly harder or easier.
For instance, problems that are computably enumerable (c.e.), like the halting problem, can be partially solved by an algorithm—i.e., the algorithm can recognize a “yes” instance but may never halt on a “no” instance.
To investigate the structure of noncomputable sets further, the theory introduces tools such as oracle machines, which are hypothetical Turing machines equipped with a “black box” that can instantly solve a specific problem. This leads to a hierarchical classification using Turing reducibility, many-one reducibility, and more. Each form of reducibility provides a lens for comparing the computational complexity of problems.
One of the key milestones in the field is the resolution of Post’s Problem, which asked whether there exist c.e. sets with Turing degrees strictly between decidable sets and the halting problem. The affirmative answer, provided independently by Friedberg and Muchnik via the priority method, revealed a rich and nuanced structure in the realm of uncomputable sets.
Another major insight worth noticing comes from the concept of Turing jumps, which formalize the idea of stepping up to a higher level of uncomputability, allowing us to study the infinite layers of computational complexity.
These ideas form the actual bedrock of modern theoretical computer science, influencing areas such as formal logic, complexity theory, algorithm design, and even the philosophy of mind and artificial intelligence. But we’re not finished yet.
Category Theory
In the mid-20th century, two mathematicians—Samuel Eilenberg and Saunders Mac Lane—introduced a revolutionary new language for mathematics. Their work in algebraic topology led to the birth of category theory, a powerful and abstract framework that reveals the deep structure of mathematical concepts by focusing not on the elements of sets or the formulas of algebra, but on the core relationships between objects.
At its heart, category theory is the mathematics of structure and transformation. Imagine a world composed of entities, called objects, and directional connections between them, known as morphisms or arrows. These arrows can be composed: if there's a morphism from A to B, and another from B to C, then there's a composed arrow from A to C.
This composition is associative, and for every object, there’s a special arrow—an identity morphism—that leaves it unchanged. This simple but profound idea allows mathematicians to describe entire domains of mathematics using just objects and arrows.
Take, for instance, the category of sets, often called Set. Its objects are sets, and its morphisms are functions between those sets. Composition is just regular function composition, and the identity morphism for any set is the identity function.
But category theory doesn’t stop with functions. It generalizes far beyond. A monoid, for example, can be seen as a category with only one object, where all morphisms are elements of the monoid, and composition is the monoid operation. This perspective reveals surprising connections between algebra and topology, logic and computation.
To move between categories, it is necessary to use functors. A functor is like a translator: it maps each object in one category to an object in another, and each morphism to a morphism, preserving the structure of composition and identities.
Some functors preserve the direction of arrows (covariant functors), while others reverse it (contravariant functors). This translation mechanism is essential in many areas of mathematics and computer science, especially in functional programming, where functors and related ideas like monads encode effects and structure code.
But category theory also tells us when two different constructions are, in some deep sense, the same. This is the job of a natural transformation—a kind of morphism between functors. Given two functors between the same categories, a natural transformation assigns to each object a morphism that makes a certain diagram commute, ensuring consistency across the whole category. If every component of this transformation is an isomorphism, then the two functors are said to be naturally isomorphic, expressing a fundamental kind of equivalence between constructions.
As mathematicians explored further, they discovered that many of the most powerful ideas in math—limits, colimits, adjoint functors—could all be described in categorical terms. These ideas are not tied to any particular kind of object like numbers or shapes, but arise from the abstract patterns of relationships and transformations.
Ultimately, category theory provides a bird’s-eye view of mathematics. Rather than diving into the details of each specific structure, it lets us zoom out and see how entire branches of mathematics relate to one another. Its influence has spread far beyond topology, reaching into logic, type theory, quantum physics, but now our focus is on theoretical computer science.
A Story of Sets
Long before the symbols and axioms of modern mathematics were formalized, human beings had an intuitive grasp of "collections." A flock of sheep, a handful of stones, or a row of soldiers—each was a group of individual things treated as a whole. But it wasn't until the 19th century that the idea of a "set" began to evolve into one of the central pillars of mathematical thought.
Though ancient thinkers like Aristotle dabbled in classifications and hierarchies (as shown in the Tree of Porphyry), it wasn't until the mid-1800s that sets were rigorously brought into the realm of mathematics.
One of the first notable steps came from the philosopher and mathematician Bernard Bolzano, who explored the paradoxes of the infinite and laid early groundwork for thinking about infinite collections. Still, his insights didn’t take root in the mathematics of his time.
The concept of infinity had long puzzled minds, from Zeno’s paradoxes in ancient Greece to the careful skepticism of Carl Friedrich Gauss, who famously insisted that infinity was a useful idea but not something that belonged within mathematics in any complete or "actual" form. For Gauss and many of his contemporaries, mathematical infinity was potential—not something finished or total.
The Birth of Set Theory and the Infinite
Yet a different perspective was emerging. In the 1870s, Georg Cantor—a German mathematician—radically redefined the mathematical landscape. In a paper published in 1874, he introduced a shocking revelation: some infinities are larger than others. While this might seem nonsensical at first glance, Cantor showed that not all infinite sets are created equal.
He proved that the set of real numbers is "uncountable"—its elements cannot be matched one-to-one with the natural numbers. This shattered centuries-old assumptions and introduced the idea of cardinality: the "size" of a set, even when that set is infinite.
Cantor didn't stop there. He developed a notation system using Hebrew letters like ℵ (Aleph) to distinguish different sizes of infinity and defined ordinal numbers to capture the position of elements in ordered sets. His exploration into what he called "transfinite numbers" met resistance from giants like Kronecker and Poincaré, who found the ideas counterintuitive, if not outright heretical. Yet the beauty and rigor of Cantor’s work could not be ignored.
At the same time, Richard Dedekind was quietly advancing his own vision. His concept of Dedekind cuts laid the foundation for real numbers, while his publications gave precise treatment to concepts like set partitions and equivalence relations. Dedekind and Cantor, though different in style, were building a new mathematical language—one where sets were not just tools, but fundamental objects.
Set theory soon became a key player in a broader movement to formalize mathematics. It was particularly appealing to logicians like Gottlob Frege, who sought to reduce arithmetic to logic. In his ambitious project, The Foundations of Arithmetic, Frege attempted to define numbers in terms of set properties. But just as this grand edifice was nearing completion, it crumbled under a simple yet devastating observation by Bertrand Russell.
Evolution of Set Theory and Its Impact on Modern Thought
Russell discovered that Frege’s system led to a contradiction: the infamous Russell’s Paradox. Consider the set of all sets that are not members of themselves.
Does this set contain itself?
If it does, then by definition it shouldn’t. If it doesn’t, then by definition it should. The contradiction exposed a fatal flaw in the idea that "for every property, there exists a set of all things having that property." Frege’s dream collapsed overnight.
This wasn’t just an isolated problem. Around the same time, mathematics was encountering multiple unsettling revelations: the independence of Euclid's parallel postulate, Gödel’s incompleteness theorems, and the existence of non-computable functions. A foundational crisis had begun, and set theory was both part of the problem—and, eventually, the solution.
To resolve the contradictions, mathematicians developed axiomatic set theory. Ernst Zermelo and Abraham Fraenkel proposed a system of axioms—rules governing how sets can be constructed—that avoided paradoxes like Russell’s. This system, known as Zermelo-Fraenkel set theory (ZF), later extended with the Axiom of Choice (ZFC), became the dominant foundation for mathematics.
From this stable base, set theory flourished. It became not only a foundation for mathematics but a playground for exploring the infinite. Mathematicians investigated the properties of large cardinals—sets so vast that their existence cannot be proven within ZFC—and began to understand the complex hierarchy of infinities. Philosophers, too, were drawn to the implications of this work, fascinated by the interplay between logic, language, and the structure of reality.
Today, set theory continues to evolve, underpinning nearly all modern mathematics, from analysis and topology to logic and computation. Its influence reaches even further—into computer science, linguistics, philosophy, and beyond, especially in AI, and that’s why we’re talking about it now in a very formal way.
What began as a curious question about collections of objects has become one of the deepest and most foundational stories in human intellectual history.
The Origins of Lambda Calculus
In his 1891 lecture Funktion und Begriff (Function and Concept), Gottlob Frege introduced a transformative perspective on the nature of functions and their arguments, which has had a lasting impact on logic and the foundations of mathematics.
Departing from the traditional subject-predicate structure of propositions, Frege proposed a function-argument analysis, wherein functions are understood as unsaturated entities that require arguments to yield values.
A pivotal insight from this work is Frege's demonstration that functions of multiple variables can be decomposed into a sequence of single-variable functions—a concept that would later be formalized as "currying", a process later popularized by Haskell Curry.
For instance, a function of two variables, f(x,y), can be reinterpreted as a function f(x) that returns another function fx(y), effectively transforming it into a chain of single-argument functions.
This approach allows for greater flexibility and abstraction in logical analysis, as it treats functions as entities that can be manipulated independently of their arguments.
Frege's emphasis on the distinction between functions and objects, and his method of analyzing complex functions through successive applications of single-variable functions, laid the groundwork for subsequent developments in formal logic, including the lambda calculus and functional programming languages.
But, What Is Currying?
The concept of currying, named after the American logician Haskell Brooks Curry, is a fundamental idea in both mathematical logic and functional programming.
While the transformation of multi-argument functions into sequences of single-argument functions was initially explored by Gottlob Frege and later formalized by Moses Schönfinkel (We will discuss about him below), it was Curry who extensively developed and popularized the concept through his work in combinatory logic.
In his seminal work, Combinatory Logic, co-authored with Robert Feys, Curry systematically studied the properties and applications of combinators—functions with no free variables—which laid the groundwork for the formalization of currying as a technique for function transformation.
In functional programming languages like Haskell, currying is not just a theoretical construct but a practical feature embedded in the language's design. In Haskell, all functions are curried by default, meaning that a function defined to take multiple arguments is inherently a series of nested single-argument functions.
For example, a function with the type signature f :: a -> b -> c is interpreted as a function that takes an argument of type a and returns another function of type b -> c. This design facilitates partial application, where supplying fewer arguments than a function expects returns a new function awaiting the remaining arguments.
Curry's contributions have had a lasting impact on the development of programming languages and the theoretical foundations of computer science. The Haskell programming language, named in his honor, embodies the principles of functional programming and currying, reflecting the enduring relevance of his work.
By conceptualizing functions as entities that can be applied to arguments one at a time, both Frege's logical framework and Curry's combinatory logic underscore the elegance and power of this approach to function application.
This insight reshaped how we think about computation, even today. In fact, it's how all modern programming languages work under the hood. Every function call in a computer is, at a low level, a series of successive applications—function to argument—just as Frege envisioned more than 100 years ago.
But things didn’t stop there. The plot is just beginning.
Foundations of Functional Computation
The early 20th century witnessed groundbreaking developments in formal logic and the theory of computation, notably through the work of Moses Schönfinkel and Alonzo Church.
In 1920, Schönfinkel introduced the concept of combinators—abstract entities designed to eliminate the need for variables in logical expressions. He demonstrated that all functional behavior could be represented using just two combinators: K and S.
The K combinator is defined such that K x y = x, effectively returning the first argument, while the S combinator is defined as S x y z = x z (y z), distributing the third argument across the first two functions. This system, known as combinatory logic, laid the foundation for a variable-free approach to computation.
Building upon these foundational ideas, Alonzo Church developed the lambda calculus in the 1930s—a formal system that employs function abstraction and application to represent computation. This system serves as a theoretical framework for understanding computation through the manipulation of functions.
The implications of lambda calculus extend beyond theoretical mathematics, influencing the development of what we call “functional programming languages”. Languages such as Haskell, Scheme, and Lisp are deeply rooted in the principles of lambda calculus, where functions are first-class citizens and computation is viewed as the evaluation of expressions. In these languages, function application and abstraction are central concepts, reflecting the lambda calculus's emphasis on function manipulation.
In our third installment, we will delve deeper into the implications of lambda calculus and explore Alonzo Church's contributions in greater detail, examining how his work has shaped the landscape of computation and programming languages.
All you need to know for now is that, in lambda calculus, functions are defined using the notation (λx.M), where x is the parameter and M is the function body. Function application is denoted by juxtaposition, and computation proceeds via beta reduction, which involves substituting the argument into the function body. For example, applying the function λx. x + 1 to the argument 2 yields (λx. x + 1) 2, which essentially reduces to 3.
These foundational concepts have profoundly influenced modern functional programming languages, such as Haskell, Scheme, and even aspects of JavaScript. In these languages, functions are first-class citizens, allowing them to be passed as arguments, returned from other functions, and assigned to variables. The principle of beta reduction underlies the evaluation strategy in these languages, enabling powerful features like higher-order functions and closures .
The elegance and simplicity of combinatory logic and lambda calculus demonstrate that complex computational behaviors can emerge from minimalistic foundations. This realization has not only advanced theoretical computer science but also inspired practical programming paradigms that emphasize the power of functions and abstraction.
“Kleene-ness is next to Gödel-ness,” Rosser wrote in his paper about the history of Lambda Calculus, nodding to the intertwined legacy of logic, computability, and the quest to formalize mathematics.
Conclusion
In this second part of our exploration into AI and reasoning, we've examined key concepts that shape computer science, logic, and mathematics. From Gödel, Turing, and Church's foundational works to the abstract structures of category theory and set theory, these ideas have had a lasting impact on modern computing.
The core of these explorations is computability. Turing's halting problem and the Church-Turing thesis revealed that some problems, like the halting problem, are undecidable and cannot be solved algorithmically. Computability theory, with its notions of Turing degrees and undecidable sets, shows the limits of what algorithms can achieve.
Category theory, with its focus on structure and transformation, has reshaped our understanding of relationships in mathematics and computation, influencing fields like functional programming and quantum physics. Set theory, particularly Cantor's work on infinity and paradoxes like Russell's, has been foundational not only in mathematics but also in philosophy and AI.
Finally, lambda calculus, combinatory logic, and functional programming have transformed computation, shaping programming languages and functional programming paradigms.
In conclusion, these foundational ideas continue to drive theoretical computer science and shape the future of computation. As we push the boundaries of AI and software engineering, these concepts will remain essential to the development of new technologies and methodologies.
👍