In the direction of Stephen Wolfram’s S combinator challenge, we define the natural numbers and subsequently basic arithmetic using S combinators alone. To do so, we investigate the computational reducibility evident in non-halting S-bird evaluations, focusing specifically on the recursive nature of the 343-bird. Along the way, we emphasize the importance of observer theory and the value of taking a new perspective on that which seems familiar.
Initialization Cells
Initialization Cells
The S,K Combinator System
The S,K Combinator System
Introducing Combinators
Introducing Combinators
A combinator is a curried function that takes indeterminate inputs; currying induces a nesting of unary functions from an -ary function, e.g. the map becomes :(XY)Z, and an indeterminate is a symbol having no particular ascribed meaning, e.g. the indeterminate can represent a number, variable, function, etc. Throughout the project, we assume combinator evaluation to occur at the leftmost-outermost expression.
The S,K combinator system consists of the S and K combinators, which can be viewed respectively in Wolfram Language form as
n
f:(XY)Z
*
f
x
The S,K combinator system consists of the S and K combinators, which can be viewed respectively in Wolfram Language form as
Out[]=
s[a_][b_][c_]a[c][b[c]] |
k[a_][b_]a |
S, the fusion function or builder, increases the LeafCount of the given expression whereas K, the constancy function or eliminator, decreases this count. We can write combinators in traditional form by replacing the brackets with parentheses, removing the parentheses surrounding one element, and capitalizing the combinator letter. Thus, and , so we can view S in traditional form as .
Since combinators take indeterminate inputs, a seemingly inhuman expression like “S(S(KSK)KK)SK” does have some meaning. Visually, we can represent this expression using an expression tree, which is read from bottom-to-top with gray cells representing composition and left (resp. right) branches corresponding to left (resp. right) applications.
s[a][b][c]~Sabc
a[c][b[c]]~ac(bc)
Sabcac(bc)
Since combinators take indeterminate inputs, a seemingly inhuman expression like “S(S(KSK)KK)SK” does have some meaning. Visually, we can represent this expression using an expression tree, which is read from bottom-to-top with gray cells representing composition and left (resp. right) branches corresponding to left (resp. right) applications.
Out[]=
By continuously evaluating or evolving this expression, again with each evaluation occurring at the leftmost-outermost expression, we see that this process halts after 5 evaluations and yields the expression K(SK). We can view the evolution process of S(S(KSK)KK)SK in both traditional and Wolfram Language form (highlighting the rule applied at each evaluation step in the latter case).
Out[]=
S(S(KSK)KK)SK |
S(KSK)KKK(SK) |
KSKK(KK)K(SK) |
SK(KK)K(SK) |
KK(KKK)(SK) |
K(SK) |
| ||||
| ||||
| ||||
| ||||
| ||||
k[s[k]] |
Why Combinators?
Why Combinators?
While pedantic and alien, the S,K combinator system is a very minimal yet powerful set of rules. Being able to produce any lambda calculus expression, S and K are Turing complete or universal, so it is (theoretically) possible to perform any computable computation with just an S,K basis. For instance, one can define the natural numbers and perform basic arithmetic using S and K, as well as represent or encode any axiomatic system (combinators are thus a substrate below axioms)! On that note, combinators are unique from other Turing complete systems in that they simplify foundational logic with reduction, treating functions/pure rewrite rules as the structural basis, or plumbing, instead of sets, hence eliminating any ontological discourse of set theory including Russell’s paradox; category theory is similar to combinatory logic in the sense that it treats morphisms as the plumbing—combinators are syntactic whereas categories are conceptual.
Of course, all other combinators are related to S and K, so the phylogeny of these creatures—like the avian tree of life—is fully characterized. In fact, stemming from Smullyan’s To Mock a Mockingbird, combinators are called birds. Thus, to study combinators is to be an ornithologist, and there are many birds in the forest to discover...
Of course, all other combinators are related to S and K, so the phylogeny of these creatures—like the avian tree of life—is fully characterized. In fact, stemming from Smullyan’s To Mock a Mockingbird, combinators are called birds. Thus, to study combinators is to be an ornithologist, and there are many birds in the forest to discover...
Out[]=
The S Combinator Challenge
The S Combinator Challenge
While the S,K combinator system is already quite profound, the S combinator alone presents some intriguing behavior. Namely, when evolving birds consisting only of S combinators, or S-birds, one either finds trivial results (a halting process) or those that are more complex (a non-halting process). One visual method for examining the evolution of these S-birds is with an S-plot, or a ListStepPlot of the Differences of the LeafCount between each evaluation of a given S-bird. For example, S-plots show that the S-bird SSSSSSSSSSS(SS)S has already halted after 150 evaluations whereas SSS(SSSSS)SSS has not.
Out[]=
|
|
The behavior of these S-birds is also captured in the expression trees of their 150th and 75th respective evaluation (the latter number being smaller for the sake visibility).
Out[]=
We now introduce some terms relevant to the evolutionary behavior of S-birds: Computational irreducibility is the property of a computation or system to be unpredictable, i.e. the outcome of a process can only being determined by allowing that process to run in its entirety—there is no shortcutting; on the contrast, computational reducibility is the property of being predictable, so there exists a shortcut to knowing the result of a system which is computationally reducible. Note that some systems, especially those that are Turing complete, can exhibit both computationally reducible and irreducible characteristics.
Given the potential computational irreducibility in S-bird evolutions, Stephen Wolfram presents the S combinator challenge, asking whether the S combinator itself constitutes a Turing complete system. In light of this problem, Stephen presents his “computer analogy” to put into perspective the behavior of evolving S-birds: Non-halting S-birds are like computers in the sense that you may receive or interpret an output but the machine keeps running all the while.
Given the potential computational irreducibility in S-bird evolutions, Stephen Wolfram presents the S combinator challenge, asking whether the S combinator itself constitutes a Turing complete system. In light of this problem, Stephen presents his “computer analogy” to put into perspective the behavior of evolving S-birds: Non-halting S-birds are like computers in the sense that you may receive or interpret an output but the machine keeps running all the while.
Recursive Natural Numbers
Recursive Natural Numbers
To approach the S combinator challenge, a quite literal natural computational starting point for S combinators is with numbers: Can the S combinator perform addition on the natural numbers? To answer this guiding question, one must first ask if there is a non-halting method to define the natural numbers. Indeed, the answer is yes if one uses recursion, for instance, of von Neumann ordinals!
Out[]=
0 = ∅ |
1 = {∅} |
2 = {∅, {∅}} |
3 = {∅, {∅}, {∅, {∅}}} |
4 = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}} |
5 = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}} |
Second, how would one define basic arithmetic like addition for such a definition? If we let and denote by the successor function , then we can define addition as . For example, .
We now possess a motivated objective in the direction of our guiding question: recursively defining the natural numbers from non-halting S-birds.
0=∅
n+1
S(n)=n⋃{n}
a+0=a,a+S(b)=S(a+b)
2+3=2+S(2)=S(2+2)=S(2+S(1))=S(S(2+1))=S(S(3))=S(4)=5
We now possess a motivated objective in the direction of our guiding question: recursively defining the natural numbers from non-halting S-birds.
The "343-Bird" and Some Visual Analysis
The "343-Bird" and Some Visual Analysis
The 343-Bird
The 343-Bird
It is a bird! It is a plane! No wait, it really is a bird...
Out[]=
This is the aerial view, or symmetrized S-plot, of the 343-bird, given by is SSS(S(SSSS)(SSS))(SS(SSS)(S(SSSS)(SSS))). Here, we can identify some bird anatomy: the beak (the top), the tail (the bottom), and individual components that look like sets of wings. (While aesthetically pleasing, all relevant information of an aerial view is of course still contained in the initial S-plot, which we can now view as being the “right side” of the bird.)
By analyzing the S-plots of many different S-birds, one gets the impression that there is inherent structure among the evolutions; the perhaps most striking one is that of the 343-bird, which seems to visually encode the recursive definition of the natural numbers we seek.
By analyzing the S-plots of many different S-birds, one gets the impression that there is inherent structure among the evolutions; the perhaps most striking one is that of the 343-bird, which seems to visually encode the recursive definition of the natural numbers we seek.
Out[]=
A Visual Definition of the Natural Numbers
A Visual Definition of the Natural Numbers
Now that we have visually identified the recursive natural numbers in the 343-bird, what do we actually define as a number? For instance, one may look at the component consisting of five 1-width columns and call this “5,” but again this is just a wing of the bird, specifically the fifth wing.
The perhaps more intuitive view of this addition is starting at tail corresponding to the first number and evaluating until the tail reached corresponds to the sum of the two given numbers; this is the perspective we will adopt when we later shift to pure symbolic notation.
Pulling Back and Pushing Forwarding
Pulling Back and Pushing Forwarding
The naming of the 343-bird comes from the S-bird it evolves from, SSS(SSSS)(SSS). Specifically, the 343-bird is identified after just 5 evaluations of this SSS(SSSS)(SSS), so we can view the 343-bird as being a pushforward of this bird.
Given the existence of something “before” the 343-bird, one must ask if there is any meaning here. By considering a pullback of SSS(SSSS)(SSS), in particular joining a series of SS with this bird, what we see is precisely the negative integers!
Note that we could refer to this entire system as the “343-bird” since it constitutes the integers, but for the purposes of this project we will stick with the S-bird we have identified with the natural numbers.
Curiously, if we pull back the 343-bird, we get a visual indication that the natural numbers are complete (this behavior occurs for no other beak except the 0-beak).
Curiously, if we pull back the 343-bird, we get a visual indication that the natural numbers are complete (this behavior occurs for no other beak except the 0-beak).
A Recursive S Combinator Definition of the Natural Numbers
A Recursive S Combinator Definition of the Natural Numbers
Tail Lengthening, a.k.a. Addition
Tail Lengthening, a.k.a. Addition
By investigating the rules at play, we can understand the tail lengthening process, i.e. building larger numbers from smaller ones. The first blue component, or the header, is constant and acts as a sort of signal to the 343-bird: As one can check, no other evaluation in the evolving 343-bird begins with SS(SS) except for the natural numbers.
The orange component is the most simple nonconstant rule, being SSS applied to a joining of the base (S(SSSS)(SSS)) with a SSS nesting with base (SS(SSS)(S(SSSS)(SSS))).
The yellow component is the most complicated rule, being a series of S applied to a joining of increasing and constant SSS nesting with base (SS(SSS)(S(SSSS)(SSS))).
The purple component is simply SS applied to the red component of the previous number, if it exists.
The green component is simply everything in between the red component and the second blue component of the previous number, if it exists; this is the only component where true recursion is used. Note that we call the orange, yellow, purple, and green components, if they exist, of the same number the tail body of that number; thus, the tail body of one number is the green component of the next number.
The second blue component, or the footer, is also constant. However, unlike the header, the footer serves no real value, as we will explore later.
Tail Recovery, a.k.a. Subtraction
Tail Recovery, a.k.a. Subtraction
Given the recursive nature of the S combinator definition of the natural numbers, we can recover all natural numbers up to and, of course, including a given number, i.e. tail recovery. For instance, it is clear to see that a number can be recovered via identifying its colored components from the respective ones of another greater (or equal) number.
However, this is not the only means of tail recovery: Since the tail body of one number is just the green component of the next number, then we can also recover a number by joining its tail head with the green component of the next number before joining the footer. We color the three components used in this tail recovery process in magenta for further distinguishing.
However, this is not the only means of tail recovery: Since the tail body of one number is just the green component of the next number, then we can also recover a number by joining its tail head with the green component of the next number before joining the footer. We color the three components used in this tail recovery process in magenta for further distinguishing.
By animating the ascending evolution of tail recovery, we also encapsulate the tail lengthening process—who knew counting could be so satisfying!
Tail Heads
Tail Heads
Verifying this result visually, we see a “headless” S-plot of the 343-bird which starts at the 11-beak (since the 10-tail is the end of our visual definition of 10).
Verifying this result visually, we see the same headless S-plot for the tail head of 0 as for the 0-tail.
Symbolic Subtraction
Symbolic Subtraction
Conclusion
Conclusion
Future Work
Future Work
This project heavily emphasized the Wolfram philosophy of observer theory—our existence is observer-dependent—allowing for an “opening of the mouth” to new perspectives on logic, linguistics, and theoretical computer science; it is the hope of the author that the results stated here have been communicated effectively enough to allow the reader to experience this “awakening.” The most obvious next step for the project would be to formally define the negative integers as well, which we already showed to exist. Also, the treatment of the 343-bird demonstrated here can and should be applied to other S-birds.
Overall, the groundwork has been laid for some exciting future projects on S-birds! There are many more “exotic” birds in the sky to study...
Overall, the groundwork has been laid for some exciting future projects on S-birds! There are many more “exotic” birds in the sky to study...
Addendum—Semantical Calculus
Addendum—Semantical Calculus
We have been working with a very minimal language, the S combinator, but how minimalistic can we go semantically? Namely, we require two symbols in addition to the “s” representing the S combinator when interpreting an S-bird, those being left and right parentheses/brackets. However, is it possible to reduce this count to only one additional symbol and form a basis of just “s” and this symbol? Here, we introduce dot notation, i.e. using a “dot” to represent composition (our symbolic choice of dot is a period). The previous aerial view shown is of the S-bird SSSS(SS(SSS))(SS)S, whose S-string, the string representing a traditional form S-bird, will be used as our primary transcription example for the three “dot rules” we present.
LDot
LDot
1
.ssss ~ SSSS
2
.ssss.ss ~ SSSS(SS
3
.ssss.ss.sss ~ SSSS(SS(SSS
4
.ssss.ss.sss.....ss ~ SSSS(SS(SSS))(SS
5
.ssss.ss.sss.....ss..s ~ SSSS(SS(SSS))(SS)S
We can verify our transcription as follows.
DDot
DDot
1
.ssss ~ SSSS
2
.ssss.ss ~ SSSS(SS)
3
.ssss.ss..sss ~ SSSS(SS(SSS))
4
.ssss.ss..sss.s ~ SSSS(SS(SSS))S
5
.ssss.ss..sss.s.ss ~ SSSS(SS(SSS))S(SS)
We can verify our transcription as follows.
A quick tangent: We can write DDot (or any other dot rule for that matter) in other forms like binary 11110110011101011 or “pure dot” notation ::::.::..:::.:.:: by simply replacing symbols. It is fun to think about the amazing computations we can now interpret from such minimalistic symbolic representations—again, it is all a matter of perspective!
PDot
PDot
1
...sss ~ SSS
2
...ss..sss ~ SS(SSS)
3
.....ssss..ss..sss ~ SSSS(SS(SSS))
4
......ssss..ss..ssss ~ SSSS(SS(SSS))S
5
.......ssss..ss..ssss.ss ~ SSSS(SS(SSS))S(SS)
We can verify our transcription as follows.
Keywords
Keywords
◼
343-Bird
◼
Birds
◼
S combinator
◼
Combinators
◼
Natural numbers
◼
Arithmetic
Acknowledgments
Acknowledgments
Special thanks to Dugan Hammock for his support and encouragement throughout the project, and to Zsombor Méder for the many great conversations. Further thanks to Stephen Wolfram for sharing his “computer analogy,” Stephanie Bowyer for clarification of program logistics, and Nik Murzin for providing an introduction to the wonderful world of birds.
References
References
1
.S. Wolfram (2021), “Combinators: A Centennial View,” In Combinators: A Centennial View. Wolfram Media, Inc.
2
.S. Wolfram (2025), “The Ruliology of Lambdas,” Stephen Wolfram Writings. https://writings.stephenwolfram.com/2025/09/the-ruliology-of-lambdas/
3
.S. Wolfram (2022), “Going below Axiomatic Mathematics,” In Metamathematics: Foundations & Physicalization. Wolfram Media, Inc.
4
.R. Smullyan (1985), To Mock a Mockingbird. Knopf.
5
.S. Wolfram (2021), “1920, 2020 and a $20,000 Prize: Announcing the S Combinator Challenge,” In Combinators: A Centennial View. Wolfram Media, Inc.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Birdwatching: A tale of S combinator arithmetic
by Russell Martinez
Wolfram Community, STAFF PICKS, January 27, 2026
https://community.wolfram.com/groups/-/m/t/3629162
by Russell Martinez
Wolfram Community, STAFF PICKS, January 27, 2026
https://community.wolfram.com/groups/-/m/t/3629162