Meaningful things are those the universe possesses a semantics for

5shminux

1Abhimanyu Pallavi Sudhir

0shminux

2the gears to ascension

4shminux

3Abhimanyu Pallavi Sudhir

2the gears to ascension

1Abhimanyu Pallavi Sudhir

0shminux

1Abhimanyu Pallavi Sudhir

1mruwnik

1Abhimanyu Pallavi Sudhir

1mruwnik

1Abhimanyu Pallavi Sudhir

New Comment

14 comments, sorted by Click to highlight new comments since: Today at 6:46 PM

Does Gödel's theorem imply that there are questions about the universe, or about mathematics, whose answers we can never learn? Are these questions at least comprehensible to us?

Note that this seems like a category error: mathematics is not physics, and building models of the universe is independent of mathematical theorems about soundness and consistency. Physicists (and humans in general) constantly use a self-contradictory patchwork of abstractions to make sense of the world. Yes, really.

If you want to investigate whether "there are questions about the universe... whose answers we can never learn", then you need to focus on learning. Specifically, a model of the universe an embedded agent has is a lossy compression of the "reality", so the question to ask would be "what kind of possible worlds compatible with observations would limit the extent of useful lossy compression?" Here is an example: most lossy image/sound and data compression algorithms are based on Digital Cosine Transform. At some point as the required compression degree gets too high, say, because we want so many details to be compressed in the number of bits that fit into the human brain, the compression fidelity might become unacceptably low, hitting the limits of our understanding, even in principle.

You sort of hint at this approach with your mention of empiricism, there is no need to worry about the Loeb obstacle at all.

I agree, and one could think of this in terms of markets: a market cannot capture all information about the world, because it is part of the world.

But I disagree that this is fundamentally unrelated -- here too the issue is that it would need to represent states of the world corresponding to what belief it expresses. Ultimately mathematics is supposed to represent the real world.

Ultimately mathematics is supposed to represent the real world.

Well, I think a better way to put it is that mathematics is sometimes a part of some models of the world. The relationship is world -> inputs -> models <-> math. Whether the part of mathematics that deals with self-reference and soundness and completeness of formal systems corresponds to an accurate and useful model of the world is not at all obvious. So, yeah, some parts of mathematics lossily represent some parts of the world. But it is a pretty weak statement.

Half-joking: Find me a mathematical statement that purports to not describe the real world and I'll show you a mathematical statement that describes patterns in constructions of symbols made of the real world. Territory comes first; math can show us perfect patterns in the territory, but by the same token, it can only ever be map. The map, being part of the territory, can then make insightful statements about itself, through many layers of patterns of patterns of patterns of patterns, but you've never seen a mathematical statement that wasn't in the territory.

~~You overstate your case. The universe contains a finite amount of incompressible information, which is strictly less than the information contained in ~~~~. That self-reference applies to the universe is obvious, because the universe contains computer programs.~~

The point is the universe is certainly a computer program, and that incompleteness applies to all computer programs (to all things with only finite incompressible information). In any case, I explained Godel with an explicitly empirical example, so I'm not sure what your point is.

I find that if I keep recursing deep enough, after a while I get to a point where I try to work out why I believe that I can believe that logic works. At which point I bounce off a wall, seeing as I'm trying to logically come up with a reason for it.

Solipsism is similar - how do you know that you're not a brain in a vat? Or in general Descartes' demon. From my (admissively most likely confused) understanding, this would be another example of self reference, albeit in a roundabout way.

Logic courses are very risk-averse to talking about philosophy. This is bad, because philosophy is the motivation/intuition for logic & TCS. This essay gives a scout's view.

Epistemic status:A computer scientist would nod through Chapters 2-5, at least after first looking at the logician for approval. Subsequent chapters take a philosophical stance, namely that expressed in the title.Contents[A rough version of Chs 1-5 post initially appeared as a math stackexchange answer and on my blog; I wrote it as I learned, and am posting more refined writing here.]

Motivation and a cringey rant [skip for the technical meat]There are several immediate philosophical questions a beginner may ask when first hearing of Gödel's incompleteness theorem, such as:

Unlike other areas of science that lay-people find weird and philosophers say absurd things about (such as relativity and quantum mechanics), these questions are honestly legitimate and relevant for AI work (the only such question that

isn'tlegitimate is "Does Gödel preclude a TOE?").Some

very wrongways to answer these questions/to introduce mathematical logic:algorithmto answer every question, not that we can't do so by other, more creative means! [Dude, do something non-algorithmic and show me.]It's a terrible habit, motivated by an averseness to risk and effort, of just giving the minimal technically-correct answer that still allows you to cover your ass and feign wisdom when someone rights their wrong question, by pompously sneering "that's a

completelydifferent question!" [You knew what my question was! You could have made it more precise too!]It's like how religious people deal with "questions we cannot answer" by making up "answers we may not question"; now religious people no longer exist, so instead we have Redditors, who've found yet another way to deal with it: "deny that the question exists".

You may go your entire life dismissing the questions that enter your mind as being imprecise, even though there are ways to tell that

there is something of non-trivial value there, never saying anything that doesn't offer the security of already having been said in a textbook to protect you ...... but hey, this way at least no one will call you a crank for entertaining weird questions.

[There are kids out there starving for an interesting problem to work on, and you're going to deny and strawman the ones you

get?!!][This is how frequentist statistics survived for so long, by the way.

Yes, it is technically true that "5% is the probability of the data given the null hypothesis, not the converse", but also completely useless to pretend that that's where the reasoning ends, because at the end of the day you need toactbased on these probabilities, and for that you need the probability of the null hypothesis being true, no matter how "arbitrary" it is to calculate this. The Bayesian is the man in the arena, while you're just in the audience going "I can't talk about being the man in the arena, I can only talk about what I'd do if Iwerethe man in the arena ... "]Gödel's first incompleteness theoremHere's a general version of Gödel's first incompleteness theorem:

That's it. It's just a particularly adversarial measurement problem. There's only two assumptions that this requires:

If Alice is a formal system (where the latter reads as "Alice's theorems are computably enumerable"), this is the classic theorem.

If Alice is just some arbitrary algorithm, then this is the Halting problem.

You can play the part of Alice and write Bob as a program on your computer.

Gödel's argument (and also e.g. Quine's paradox) works by introducing self-reference through logical correlation. You can't even have beliefs on "the rest of the world", because the rest of the world can contain models of you.Gödel's second incompleteness theoremRealistically, if Alice were an enumerator for a formal system, and Bob was a program "halt iff Alice proves I don't halt", then Bob would never halt, and Alice would be unable to prove this fact. But surely if this were

usrunning the enumerator, we would realize this ("Clearly the only possibility is that Bob doesn't halt but I don't prove this"). Is this a limitation of formal systems?Of course not; we can formalize this reflective reasoning too:

Bob halts⟹Alice proved Bob doesn't halt⟹Bob doesn't halt⟹Contradiction∴Bob doesn't haltAnd you realize the implicit assumption made in this reasoning, that if Alice proves something, it is true [i.e. Alice is sound]. Alice is not allowed to believe this. This is Gödel's second theorem.

Notice how we are only allowed to deduce that Bob never halts when Bob depends on the beliefs of the proof enumerator/Alice

only, NOT when Bob depends on our more reflective belief. We are allowed to believe in the soundness of this proof enumerator/Alice, we are not allowed to believe in the soundness of our "entire" belief.Semantics and truthDoes a person (or computer) really "compute", do they really have "beliefs" and "preferences", or are they just a physical process?

Any work with agents/computer science necessarily involves a layer of "interpretation" to assign meaning to their actions, or to decide that their beliefs are "true".

If Bob models Alice, he judges a thing imagined by her to be "True" if he believes it (or rather his translation of it). This is the definition of truth according to "Convention T"/"the semantic theory of truth". There are other definitions of truth, but interpretation is fundamental to all of them.

Now that we have defined truth, we can formulate the Liar paradox.

This leads to "Tarski's theorem": Alice

can't even ask"Is P true?", can't even formulate a general notion of truth (of Bob believing his interpretation of her statement), because when truth is relative in this sense, formulating truth would lead to a tower of increasing complexity: "Is P true?" really asks "Would Bob answer YES if I asked him P?", but Bob then needs to interpretthissentence [answerthisquestion], ad infinitum.Exercisesareprograms, namely their theorem enumerators. But also theories are capable of proving things about programs, just as they are capable of proving things about stronger theories; they just don't believe those things themselves.]Arithmetical hierarchy" -- the hierarchy of FOL sentences (equivalently FOL-definable sets): a Σn sentence is one that starts with some exists then alternates n−1 times between consecutive sequences of foralls and exists; a Πn sentence is one that starts with some foralls then alternates n−1 times between consecutive sequences of exists and foralls.shockingthat Löb's theorem has such a thing as an application.]Reflection and ordinalsEliezer has suggested that Gödel's second theorem can be intuitively understood as a statement of humility: "you can't believe something just because you believe it" (perhaps suggesting that we should therefore find the theorem unsurprising as a result). I'm not sure that this is a correct explanation; the word "because" is rather trippy here, and you also can't believe that you're right 80% of the time or 20% or something (or have a calibration map). I think it is a fake explanation; it's like saying neural networks are to be expected because they look like brains or because the world is hierarchical or something. It's an attempt to

make Gödel intuitive, rather thanmake your intuition model Gödel. Similar analogies to education systems trying to "make math fun", when they should be training the children to naturally be excited about math.The correct understanding of Gödel's second theorem -- as well as Tarski's theorem, and Löb's theorem -- I think, is that

you are not allowed to have beliefs about your beliefs. Or rather: you are not allowed to have beliefs about your truest, most final beliefs.Because your beliefs just can't be

big enoughto contain themselves. Even in the most basic setting -- if you have a universe that is in one of two states, a sample space of S={0,1} but then you add an agent that believes one of those states to be true, your sample space of the universeincludingthat agent needs to be S2. If you want the agent's beliefs to be complete forthissample space, you then go up to S4, etc.But at no point can you ask the agent's beliefs to be

fullycomplete -- to be complete foritself. There's just not enough space, and just as the traditional Cantor diagonalization is a proof of "not enough space" for cardinalities, the diagonalization arguments found in Gödel proofs are natural generalizations of this idea.Don't get me wrong -- you can certainly have beliefs like "I believe that I believe there is a dragon", etc. It's just that this will always be at a higher "level" than the earlier set of beliefs, so that earlier set of beliefs doesn't express the set of

allyour beliefs, so you can never quite quantify overallyour beliefs, at all levels. The reason why it's OK for us to "informally believe but not prove that Bob never halts" has nothing to do with that belief being informal, it is because the formal system no longer represents our true belief, and Bob is only trying to fuck with our formal system, not our true belief. But Bob can always fuck with our true beliefs if he wants.How far can we actually reflect on our beliefs? You may think one can have beliefs about beliefs, beliefs about beliefs about beliefs, etc. -- for any integer. This is equivalent to thinking "At t = 0, I think Bob will halt; at t = 1, I realize this belief of mine means that Bob will not halt; at t =3, I reflect on

thatand realize that Bobwillhalt, ... " But are not constrained to be so stupid, we can also predict all our future such reflections and immediately, in finite time, form a belief about all the reflections that wewouldhave done if we had been so simplistic. We could call this reflection ω, and we can accomplish it in t = 1, then at t = 2 we reflect onthat...In general, we can reflect up to any

ordinal. For the {0,1} toy model described earlier, the idea is that the set of beliefs at stage ω would be SN (aka N→S), i.e. agent ω's belief is a function that takes in a natural number i and gives agent i's belief [which is itself a vector of size 2i−1] ... but there's a caveat! Not every function/binary sequence can realistically represent the beliefs of a computable agent, only thecomputableones can. The beliefs of each agent is aprogram.[Let that sink in.]

Here are some general constructions for agents that reflect up to particular ordinals (f is some pre-specified computable function that defines how the agent reflects).

OK I've written these programs in ridiculous short-hand -- in reality the program for agent ν is a function that takes as input any ordinal μ<ν and give as output the program for agent μ.

But for a general ordinal, this function may not be computable! In particular, since any computable ordinals may be inputted as the code for the program that decides the corresponding order, this means that the belief "program" for ωCK can take any program as input, discover what order it computes, and output that program's belief program. This is a violation of Rice's theorem, which says that there is no algorithm that can determine what any algorithm does [obviously!], so "agent ωCK" isn't a computable program.

You can only reflect up to computable ordinals. The Church-Kleene Ordinal places a hard cap on reflection; you can get arbitrarily close to it (i.e. exceed every computable ordinal), but never reach it.This wisdom transfers over to strengthening a theory by reflecting on it. There is a program that enumerates T+N (the N-th reflection of T) for all computable ordinals N, but no more. The minimal length of this program (Kolmogorov complexity) is non-decreasing in N, and approaches ∞ as N→ωCK.

Chaitin and complexityREALITY CHECK: you

cannotreflect up to any arbitrary computable ordinal [a program that can reflect up to any arbitrary computable ordinal has complexity ωCK, i.e. not a program]. Or rather:youcannot reflect up to any arbitrary computable ordinal -- you are some program, and you are bounded by whatever your computational power is.Things are not so hopeless. You can build a computer that is better than you -- so in the end, you are only limited by the computational power of the universe/of physics.

But don't we understand, intuitively, transfinite induction up to arbitrary ordinals?No -- because you are not capable of actually reasoning with these extremely strong theories, so such a "belief" has no meaning, much like you can't reason with an uncomputable theory. You can

imaginesuch a theory, but you cannot believe it.We can formalize these complexity-theoretic considerations:

Chaitin's incompleteness theorem.No program of length L can determine the semantics of programs of algorithmic complexity even slightly over L.The natural question to ask here: is the converse true?

all arithmetical sentencesof length <L -- are decidable by ZF+N?Empiricism and the LöbstacleThe "Löbstacle" can generally be defined as the question, "What is the rational basis for reflection and self-improvement (building a better computer)?" Even if we give a rational basis for reflection up to our

owncomplexity, how could we possibly give a rational basis for "trusting the universe's computations"? -- if the universe is more complex than us, how can we assign semantics to it?I believe the answer is

empiricism. There isn't a way to say this without sounding like a deranged hippie, but I'll try: if a small program has access to a larger program (can run it and use its outputs), then for all intents and purposes, the latter can be considered a part of it (just like Alice cannot predict the actions of Bob, because by being able to read her mind, he is actually being more complex than her).It's like, if we were a formal system we would have an axiom:

whatever is observed is valid-- and this gives us access to all the computations the universe has performed yet.This is far from a formalized solution to the Löbstacle, but I think it's the right idea.

And that's all I'll say.

[ETA: not

allempiricism is this. Empiricism also addresses regular statistical uncertainty, i.e. uncertainty about syntax, not just algorithmic uncertainty, i.e. uncertainty about semantics.]General readingThings I read:

Was mathematics invented or discovered?Gödel's theorem and informationConsistently reflecting on decision theoryBayesian probability is for things that are space-like separated from youMight also be worth reading on (but I haven't covered, because I don't understand the importance of) proof-theoretic ordinals. I believe a standard source is Rathjen.