It’s the Church-Turing Thesis.
As an overview (which I do not fully understand), Alonzo Church and Alan Turing both independently proved something about “construction”, “generation”, or even I think you could explore the notion, “creation”, “induction”, or “existence”; if you want to think of it various ways.
In a lot of modern mathematics, it is actually more common to assume the existence of all objects that will be used, and only weakly or vaguely define them. This has to do with philosophical issues in any foundationalist cause or program, the famous, classic (and maybe even, at this point, obvious and slightly boring) problem of infinite causal regress (1) - give us your Euclidean axioms, to any system: but where did they come from? And, what is “formality”, anyway? The distinction between “pure objective logical necessity” and “just casual, flexible, informal human thinking” may fall apart, when examined more closely - and, though there have been presumably many, I at least know of Wittgenstein, and I think a school of thought called “pragmatism”, including Austen and Putnam (not totally sure), which basically moved into a type of anti-foundationalist view on the foundations of mathematics, and truth - contra logical “formalists”, especially Bertrand Russell and Gottlob Frege, and early Wittgenstein, as the center, who (I think) tried to solve the problem of infinite regress through what you could call a “monad”, possibly? An indisputable, self-evident, trivial to the point of meaningless, qua tautological fact, statement, assertion, or a collection of them, from which you can build the whole flora and fauna of expressions, assertions, truth and propositions as we know - the entire world.
Late Wittgenstein and others (I believe), stopped believing in the “reification” of mathematics, that numbers are a real thing, in a Platonic way, the dictates of our universe, from whence they came we know not, but it has a quasi-religious spirit to it, like Newton’s Laws were the guidebook God decided on when he gave the universe its foundational charter.
Late Wittgenstein, and the centrality of games, and rules, is heavily about how rules are contextual, and depend profoundly on things like who’s doing the interpretation (I think).
The best continuation of this entire train of thought (I know of) is the contemporary French logical Girard, who wrote an entire book on it (I intend to study).
https://link.springer.com/chapter/10.1007/3-540-44802-0_3
https://plato.stanford.edu/entries/logic-dialogical/
But it might have some relationship to the concept of a “logical alien” - if there are bounds to “reason” at all, if “logic” conforms to any actual obligatory benchmark of something, or if all rule-following is just that, and as Wittgenstein might say, anything we can even conceive of, has reality as a hypothetical; but reason itself is always hypothetical, until a human interpreter chooses a context or a set of rules by which they judge it, its correspondence, if they think it holds up.
Maybe, this can be a metaphor of a camera - or a traditional 3-way distinction in semiotics, and theories of meaning, even, I think, Aristotle - that “meaning” is something like a thing, its referent, and critically, the medium, substrate, vessel, person, or connector who draws, holds, maintains the pairing / association between the two. See Pierre Levy, “IEML”, the semiotic triad of “Sign-Being-Thing” (SBT).
The metaphor of a camera comes into play, because a camera can be turned into the entire world, but can never film itself. It opens a question about complex systems - if “information” is necessarily relative - that it is about how some absolute information engages in a confluence with some other information (some context of interpretation), this means, there can never be “absolute” or “intrinsic” information (or meaning), as a one-dimensional thing: the “cosmological constant” (in grandiose terms) of meaning or existence or the world is 2, or a the ability to express a difference between more than one thing. In a way, “1” is like “0”, in the sense that, you can’t make sound in the vacuum of space: no information is possible when it can’t impinge on something else: and like the camera, it can’t really impinge on itself (otherwise, it’s not really just one thing.)
The ingenious category theorist David I. Spivak at MIT has said a similar idea, to quote him, “Outside of mathematics, a rule cannot have meaning outside of the context operationalizing it.” I think Saul Kripke may have drawn out the specific focus on rules in Wittgenstein’s PI, in his own famous book “Wittgenstein and Rule-Following”, jocularly referred to as “Kripkestein”.
While it may prove to be a mere passing trademark of an intellectual current in our time, you can follow what were long ago distinctively separated fields of thought into a single point they have a confluence at, philosophically - languages and computer programs, codes, and even DNA, are formal languages - formal languages, computers and machines, algorithms, board games, systems of interaction modelable as mathematical game theory, all of mathematics, logic, and therefore theories of propositional meaning and truth, come together as formal systems, like set theory, theories of axioms and the foundations of mathematics - and these topics can be abstracted further and farther, uniting physical systems and their states, and the information required to describe them, and biological systems as well, with abstract mathematics, as information theory.
The more abstract one goes, one climbs into abstract algebra, higher category theory, and topos theory, and modern categorical logic and type theories as a foundation to rules and formal systems, truth and proofs. But the question of following rules - of how do you know you are following the rules - what proves or gives it justification - and where did the rules come from, what are their rules, abates - could a computer represent a perfect reasoning machine, an actual transformation on states, proving something is real or possible or obtainable or constructible or generatable? I believe this is the idea of “constructive mathematics”, where there is no concept of “truth”, abstractly - just a physical requirement that you can actually make (for example, compute, on a machine) anything you suggest exists - the rules of construction are simply the properties of the system - the capabilities of the machine, gizmo, contraption, doing the actual transformations.
But there’s always the problem of the camera: even computers require an interpreter. A computer can store a book in binary code - but a human has to do the final layer of re-translation, it was the human that decided what binary code would be read as each letter in the alphabet of their language. This is why a “computer”, as a modern idea, is a deception: it does not need to have a screen, or a mouse, or be made of silicon chips, or even use electricity. The common suggestion of an abacus as an early example of a computer may seem befuddling until you see things this way: there is no difference when you realize that a computer depends on human interpretation more than you may have realized - like a language, or the axioms of a new mathematical system or theory, it’s like a “boomerang” where there has to be a system already capable of constructing a system that can generate new meaning, to set it forth into the world, plan how its states will transform, and what will be the attendant, corresponding interpretation of those changed states, in accordance with the design or plan that the initiator - the one who confers their own meaning into some system that is really just a subset of all the possible meaning and ideas they have in their mind, can have in their world - grants it, intends to receive.
You can see how inseparable a code is from its interpreter by designing your own little codes:
A B A A B
I can ask, what’s the “inherent” information, in the pattern? Is it, “Well, they’re 3 A’s, and 2 B’s”, at least (this is called Kolmogorov complexity, trying to reduce your description of information into the smallest form). But aye, there’s the rub: a Kolmogorov-type “compression” (it is literally used for compression in computer files, to retain the same total information, reconstructrible, but in a logically smaller form, taking up less space, in memory) has a terrible flaw, for someone trying to construct “meaning” or “information” ex nihilo: it assumes there is someone who knows the algorithm to reconstruct the original message, from the compressed version. If there’s not, the message means nothing except what it now says: 3A 2B, or whatever. And that’s the thing: the information was reduced in the code - but surely there is something in the interpreter that has some form or representation of that information - you can only transfer information out of your line of sight, but you can’t actually lose it. Wittgenstein calls this the “limits of your language”; there is no “outside” to a system of concepts; they can only relate to one another intensionally (as in, “by an inherent relation to one another as defined by the rules of the system they exist within, as elements of): but there has to be something “outside” them, governing them.. like a chicken-egg scenario, every human has to be born of another human; so who was the first human, and how were they born?
The Church Turing thesis (as I understand it) is less about an upper bound on the abilities of a computer, but on a lower bound on the requirements of a computer, or an upper bound on the bootstrapping capabilities of any “constructive system”, and I think it demonstrates ipso facto truth, meaning, true, by virtue of itself:
If you want to “go Kolmogorov” and reduce descriptions of the world to the simplest possible idea - a monad - from which all ideas can irrupt - you are under an illusion: for it is the human interpreter, with all their implicit knowledge they have within them, who conducts the construction of new “objects” (propositions, ideas) - be it on paper, or in their mind - they are deceiving themselves - there is already much more information in the pot than they realize or care to see.
So try to subtract yourself from the equation: have a physical system with no “thinking” abilities, use your supposed axioms to construct a bunch of objects that can be interpreted as the elements of logic, truth, and meaning - like Von Neumann or Godel’s “constructible universes”, recursive functions defined on sets that can be interpreted to on their own generate, or imply the existence of, objects like functions, quantifiers, set objects, which can be used to define first order logic, then all human ideas, meaning and propositions: have a computer carry out the generation, instead of a human by hand. You haven’t solved the problem of axioms requiring themselves to be able to exist: a human has to program the rules of construction into the computer, which would have identical structure to some of the logical ideas you were trying to generate in your supposed “minimal system”, basically. Perhaps (I do not know), Godel’s incompleteness theorem could be seen as but one example of this “principle of the camera”: for some of the reasons outlined above, you could never have a truly “complete” logical system, unless it is Wittgenstein’s “private world/private language”: the world of thoughts you already exist in, already are trapped in, in your mind: any subset of thought you try to plant on a page is just there because of a “prime mover” (you), only generates meaning to you because of the meaning you already have, in you. It’s like a philosophical parallel to special relativity: we do not have a shared common reality, but for each of us, there is only one real reality (our own solipsistic dream that is life).
The Church Turing thesis (I believe) is pointing out some sort of contradiction (I haven’t studied the mathematics enough yet, but I am learning) that if a “constructive system” is able to construct another constructive system, then that constructive system already had the constructive capability of the system it constructed. It’s a problem with bootstrapping: a weak system (under constrained rules) cannot generate an object (under the rules of interpretation being enforced) which acts like a more powerful constructive object - to escape the confines of its constructive world, to enhance its own capability farther (on a significant, high level, not something small, local, yet illusory). We have an if-and-only-if condition here, a circularity: whatever constructive object you want to construct (like Kolmogorov, a shorter description for a bigger thing), you already need an object of that constructive capability to construct it. And the obverse: a constructive system may have an infinitude of different versions, but they are all - in their capability for construction - basically the same single thing, they can all derive each other (see “universal Turing machine”). I believe the broadest way to express the Thesis is, “meaning cannot be constructed ex nihilo” - like the quote by David Spivak above.
QED.
