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?