# Axiomatically, what characterizes “recursion”?

My question is admittedly simple, but the desire is to have an insightful view on it behind a conventional definition.

In different foundational or axiomatic systems, I have come to consider “compositionality” as possibly the single most general concept to use as a structuring principle, in any system that gives rise to increasingly rich amounts of information. “Composition” is a highly general, even cognitive, idea of, “put two things together, and call it a new thing”.

The way I see it, whatever concepts or rules you start out some minimal system which is meant to define more complex informational structures, there is this fundamental “impasse”, which I think is like the Church-Turing thesis, where it’s actually hard or nigh impossible to derive a rule, which was not already implicitly there as a rule of interpretation, to begin with.

For example, the simplest possible “compositional” / “combinatorial” system is something like, the free infinite commutative(/symmetric) monoid or semi group, I think, in abstract algebra. You have some things, you can put them together to make another thing. That’s it.

Mathematically, you don’t have more rules of interpretation on if any of those elements generated are themselves “interesting” or useful in some way - they’re just “words” (compositions of elements).

I think it’s common to define functions in terms of sets - like a set of tuples, where the first element is the domain, and the second element is the codomain. Thus, a “function” is a set of ordered pairs.

But that requires a human interpreter to understand that way of writing down functional associations.

What if you wanted to have a computer do it instead?

I’m not sure, but it doesn’t sound elegant - maybe you need a program that’s checking every set generated in the cumulative hierarchy (of composition) - of it is a set of ordered 2-sets, then it recognizes that as a function. Perhaps you can also “use” the functions - you can specify a function (perhaps each object has a hash to identify it) and call it on an object in its domain: the program knows to return the corresponding value.

So, you generated / constructed functions from nothing but the composition of elements (basically, power sets, subsets of sets). But you didn’t really - your computer program already had a more robust program to run it, that had an “if” conditional, a match / equality operator, a true/false object, a “for all” quantifier, a concept of set size (cardinality), and even somehow the idea that a function paired with an element in its domain “is associated with the corresponding element in its codomain”. You can’t construct a mathematically rich system unless you already have a system of equivalent mathematical richness. Right?

I think we might be able to build up the idea of a universal Turing machine by considering very simple games or procedures, and adding in some fundamental capability, one at a time.

Imagine dropping colored pebbles in a row, perhaps at random. Ok. Not much to say. Not too much change or order, as time goes on.

Now: if we want to try to enhance how the system behaves by minimally importing rules or concepts from somewhere else (like, “every third stone shall be blue”), the first thing I am (only prematurely) confident we need is the ability to read our own sequence, and act based on a condition of that sequence - so, you have a ‘read’ and an ‘if’ command, and a concept of equality, let’s say. (Maybe, any of those three things alone would not be useful, so somehow we can bundle them together into a single thing?)

I think right now we have a ‘context-sensitive grammar’ (Chomsky type-1, I think?). If we assume infinite colors for the marbles, we have Chomsky type-0, Turing complete, yes? If we have finite colors, we require infinite loops in our instructions? Expressions that say things like “do while”? (I guess that was implied by the idea that we were dropping stones in a line continuously, with no intention of stopping or rules for the game to ‘end’ / halt).

I guess I am trying to see more clearly what might be a cleaner reduction on where “recursion” or infinite loops could come in - as there are different ways of presenting it. Is it a function which can call itself? Is it implied by any formal system with infinite starting elements, like my pebble game?

Someone told me “recursion” can even be expressed as a “fixed point”? “In untyped lambda calculus,” a fixed-point combinatorial such as the Y-combinator “is used to define recursion” (1).

Can someone help me understand: how can you minimally specify what recursion really is, from an axiomatic perspective? Is the real point of recursion “infinitude”, in which case, you don’t need the concept if you already assume infinite elements? Is recursion a condition on finite sets for them to be able to imply/construct/determine infinite ones?

But is that just a mirror image, since a function which calls itself, has to actually be called an “infinite” number of times, to actually produce “infinite” elements.. can we say that there is no such “thing” as infinity, from a computability perspective - only halting, if something will stop on its own, or else, outer forces will have to stop it (someone has to turn off the machine / stop playing the game)?

If we try to reduce these systems to the fewest possible elements, I am considering choosing “rules” as the only existing objects in the system. A rule calls another rule: Rule 1: If Rule 2, Rule 3. This could be either that if Rule 2 has been acted on, next you just act on Rule 3; or it can be a swapping rule, where you can swap out Rule 2 if it is present.

This similarly I think reduces to the Universal Turing Machine - you can “read” in a way (you know what elements are present) - you can “write” (you can do, likes function, act on something, change in some way) - and you have conditions (if-statements). If we abandon a need to identify “recursion” and just focus on “halting” instead, then I think that makes “recursion” clearer. Any collection of rules that does not have some circularity, where one rule can lead back to itself, will not halt, and is “recursive” in the sense of a function calling itself (even if indirectly / via a chain of functions).

What interests me is that you can make all these different systems like anti-foundational set theory and study the resulting behavior of that system. The Church-Turing thesis tells us that the Universal Turing Machine will be the maximum possible, of any such game or collection of rules. Or does it?

Could there be all kinds of games we just haven’t explored yet, based on subtle changes in this or that simple scenario? It feels like a huge avenue for creative tinkering and poking around, navigating to uncharted territories.

But it makes me think that the Turing Machine maybe can be expressed in fewer than four “things”. Maybe that’s what type theory is for - the modern attempt to establish the minimum necessary, in any constructive system?

A lot to unpack here! It's hard to extract a clear question from your post, but I will just comment on a few of your statements:

the Church-Turing thesis, where it’s actually hard or nigh impossible to derive a rule, which was not already implicitly there as a rule of interpretation, to begin with

The Church-Turing thesis tells us that the Universal Turing Machine will be the maximum possible

Your interpretation of the Church-Turing thesis is not correct. For example, we know that it's possible to define many models of computation stronger than Turing machines, and plenty of researchers have studied such models. The point of the Church-Turing thesis is to formalize the intuitive notion of "effectively calculable" that was common parlance among mathematicians by the early 1900s; at the time, it basically meant "computable (by a human) by following routine algorithm" but no one had a precise definition. The Church-Turing thesis is, no more and no less, the proposal to identify "effectively calculable" with the formal definitions "computable by a Turing machine" or "computable by a lambda calculus expression". See the Stanford Encyclopedia of Philosophy's article on the topic for a good overview.

For example, the simplest possible “compositional” / “combinatorial” system is something like, the free infinite commutative(/symmetric) monoid or semi group

you don’t have more rules of interpretation on if any of those elements generated are themselves “interesting” or useful in some way

Actually, this structure actually already requires recursion to construct. The rule of interpretation here is that we know that every element of the free monoid was generated by some finite application of concatenation of individual elements. And this is also the core of what recursion is about.

Axiomatically, what characterizes “recursion”?

In short: the core of recursion is inductive constructions. It's the idea that every element of a set is constructed via some finite number of applications of some list of allowed rules.

Mathematicians working on formal languages for proofs have found that this is sufficient -- you might be interested in the Calculus of inductive constructions which is used by the proof assistant Coq; it's been found that this very simple system is enough to formalize most properties of modern mathematics. The core idea of the calculus of inductive constructions is the idea that you can give an inductive definition, like "a string is either an empty string, or a character followed by a string" and interpret all ways of finitely constructing an object from that inductive definition.

• Thank you, I will follow up on this and try to correct my question and its claims in light of your feedback. Thank you very much. Commented Jun 18, 2023 at 17:57
• You are welcome. Commented Jun 18, 2023 at 18:52
• Recursion is about a function calling itself. It is more clear in the context of arithmetic, see the Peano axioms en.wikipedia.org/wiki/Peano_axioms. Commented Jun 19, 2023 at 7:06