I am picturing a sequence of symbols S, of length L. The symbols are from alphabet A, with k distinct symbols. The symbols can repeat, there can also be 0 of a particular symbol in sequence S.

This is a question I am deeply preoccupied with that I am still trying to slowly budge over like a heavy rock.

I believe one of the necessary requirements of a universal Turing machine is conditionals, like it has to be able to choose between different actions depending on what it gets as input. In a sense, that is also a kind of memory, since it is storing the instructions for what it will do, in either case.

The general universal aim of “parsing” or reconstructing (whatever you want to call it) an input sequence is basically to rearrange it in what appears to be a more ordered form. This has a lot to do with things like Kolmogorov complexity, and Claude Shannon’s idea of entropy: an infinite repeating sequence of 100100100100 is actually really simple, once parsed. On a higher level, some language / set of symbols / instruction basically says, “write 100 over and over again”.

I have been struggling to think about how those kinds of instructions themselves can be formally written. I am wrestling with the problem of meta-languages. It feels neat and assumption-less enough to say one has a set of some symbols and can put them in sequences. But once you start describing the rules by which they are generated, or, the inherent dual idea, the rules by which a sequence is “parsed” / rearranged into the symbolic representation that increases a sense of order, there is this confusing issue where you have to figure out how to ground the rules, syntax of that meta-language, too.

For example, Chomsky’s transformation rules syntax is pretty minimal, something like a -> bc. But then, what is the syntactic definition for this transformation syntax? A human understands it intuitively. But a computer? You can give it these phrase structure rules, but it will already need a program in place to parse those rules and be able to operationalize them.

Similar to the Turing machine, if you are obsessed with having foundations, with never arbitrarily accepting something but seeing from when it came, I so far have not learned how to get to these very foundational systems like a description of a Turing machine, a formal description of syntactic transformation rules, from something even less. I have been exploring a ton constructible universes, which fascinate me, under the idea that because they generate all structures, there are sets in there with the structure of various functions, instructions, “programs”.

Even if there are, I right now still don’t see how you could use such a program if you came across one, unless it was being parsed / used by a system that already has some of this minimal capabilities like conditions and memory.

Is there any clear thesis or proof on this matter? Do logical foundations often have a sort of threshold where if a human permits themselves enough ability to assume, to make a small, careful set of axioms, the rest of a whole theory can be derived; but beneath that, there‘a no logically rigorous way to start with almost zero rules, assumptions, structure, and somehow bootstrap/generate from there to the construction of those needed concepts, defined as sets or as functions, like conditions?

Is this a known finding or idea? Is there a more abstract way to say it than Turing’s specific machine with the read-write commands and the tape? I’m wondering if the idea is like, below a certain information threshold, you are incapable of even expressing the idea of what a program/instruction is: you are stuck in no man’s land, you can’t specify a simple program that could itself act like a Turing machine, if you did not already have the capability of a Turing machine?

I feel like I haven’t approached it from this philosophical angle before. Is this some known philosophical semi-“paradox”, where it appears recursively that the only thing that could have created something with certain properties would need to already have those properties; the question of foundations are a total impasse. If you have some fundamental cognitive/linguistic/expressive/creative ability, you are in the domain of creation; if you do not, it’s impossible to get to B from A. A is a black hole you can’t get out of.

Is this a known idea? Is it impossible for a foundations for mathematics to be at a certain level of information simplicity - it must attain a certain level of capability from the beginning, as axioms, otherwise, it is no theory of mathematics at all?

I believe this was a major focus of Gödel’s, as well.

  • The name Gödel appears in yer post. All clear! Gödel's work, cogito, clearly validates the OP's aims and objectives, but probably not im the same way the OP thinks. A metalanguage proposed is gonna be different from language in only trivial ways ... cogito. May 21 at 1:31
  • My question strikes me as clear. I don’t find your comment clear. What part of my post is hard to understand? I can make it clearer for you, if you can be more clear about what you find unclear. Thanks.
    – hmltn
    May 21 at 16:05
  • I am pretty sure the answer is that this is what was a big deal about Turing’s proof about universal Turing machines. He proved that a Turing machine is necessary and sufficient to engage in kind of unrestricted, flexible computation that can accommodate a whole universe of programs / computational systems / constructive systems. Any system with certain minimum abstract properties/capabilities is essentially identical to a Turing machine. Also, a Turing machine can construct anything other Turing machine.
    – hmltn
    May 21 at 16:10
  • I had before only thought this meant something like, if a constructive system is not a Turing machine, it can still have non-trivial capability; can construct many expressions/programs/patterns, can generate information. But it is somehow more limited. The Turing machine is this apex of generative capacity where the machine can recursively self-generate. It reminds of infinite numbers, where I think a subset has the same size as the set.
    – hmltn
    May 21 at 16:12
  • But now I realize it might mean a little more than I thought? I need to think more. But it’s like this huge asymptotic / “quantum” leap from the realm of bounded to unbounded. That’s why it reminds me so much of set theory and cardinalities of sets. (I think) there is this very abstract idea where two sets don’t have a coherent “translation” between them. Maybe, we imagine a recursive set of rules. Even if it has like 10 levels of nested, as long as you find a recursive function that can generate those rules, you can specify it finitely. Some recursive processes are too recursive,
    – hmltn
    May 21 at 16:19

1 Answer 1


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).



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:


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.


  • +1 because I can be guaranteed the OP was looking for this answer. But, good answers usually more broadly explain why the answer stands. I strongly encourage you to break down your questions and post them individually. Our knowledge base could stand to explore the philosophy of computers more thoroughly. Good luck!
    – J D
    May 22 at 18:44
  • Thank you. I will, with your encouragement, break them into separated questions as revisions, but my brain-dumps are literally indispensable as an aid to my own thinking. Like the rubber duck principle to programmers, trying to wrap up my thinking for the day by ‘presenting’ it to a public forum is actually how i crack the code, just when I thought I could go no further. Then it is finally time to rest and retire for the day/night. BUT I will and should go back and clean them up. Thanks for your message.
    – hmltn
    May 22 at 18:56
  • :D I 100% agree with your methods. But stream of consciousness makes metaphysics even more confusing than it already is for us simple minded folk. ; )
    – J D
    May 22 at 19:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .