garak

@garak

Lorem Ipsem

  • hic/haec/hoc

A sequence of bit-flips on Cohost's servers, such as those caused by cosmic radiation. There's no evidence of anything more.

Also responsible for @carpediem, find out the secret reason why each day is special.

log inask
garak
@garak

Chaitin's Constant

Ω

There is a number, somewhere between 0 and 1. It is well-founded and exactly defined. It has a specific value. We will never know what that is.

  • The first 64 digits (in binary) have been found.
  • Knowing the first several digits will find the answer to any unsolved mathematical problem. The Goldbach Conjecture, unsolved since 1742, would only take 1,200 digits or so.
  • Knowing too many digits of this numbers would, in layman's terms, reveal the true name of god and end the world.
  • We don't know what constitutes "too many," as that knowledge is itself equally unattainable by mortals.

I swear this is actual, legitimate mathematics and not some Jorge Luis Borges-ass piece of short fiction.

This number is named Chaitin's Constant after its inventor, Gregory Chaitin, and is usually written Ω (I assume for its eschatological implications). It represents, roughly, the probability that a randomly-constructed Turing Machine will be one that halts. There are a lot of details to make that actually work, but you can gloss over them and still get the idea.

The main idea is that knowing this number solves the Halting Problem. You can just run All The Turing Machines in parallel. With Chaitin's Constant, you know how many will halt so you can simply wait for that many to halt and know the rest of them don't. Now you know which Turing Machines will run forever. Which cannot be known.

Technically the exact value of Chaitin's Constant depends on how you define your model of computation. And actually each model of computation has its own Chaitin's Constant. There are some constraints: you must be able to represent each Turing Machine as a binary string, and no such string can be the prefix of another such string; this turns "random binary string" into "binary search on all Turing Machines," which is what makes this actually work in practice, and behave like a probability.

As a result, there are actually many Chaitin's Constants, one for each encoding of machines as strings. They are infinitely many; they're littered all over the number line.

Knowing whether an arbitrary Turing Machine will halt is the canonical example of a question which provably cannot be answered.1 This un-answerability tends to be infectious: anything which might be used to help determine whether a Turing Machine halts must itself also be unattainable. Chaitin's Constant is, by design, deeply entangled with computability and must enshroud itself in mystery as a result.

So mysterious, in fact, that it is the most random a number can be. If you try to write it in decimal, all of the digits must be equally likely, otherwise that sheds too much light on its possible value and breaks the laws of the universe.

As it turns out, all numbers that are as random as a Chaitin's Constant are a Chaitin's Constant for some model of computation. That's the thing that blows my mind: any numeric constant which cannot be compressed inherently describes a model of computation.

Bonus Fact: Does knowing this number actually reveal the name of god and end the world? Technically yes. Because you won't find it.

The way that mathematics views "truth," the statement "X causes Y" is true unless there is a counterexample where X happens and Y does not. If X never happens, then "X causes Y" is true, a situation called a "vacuous truth."

We define truth this way because it makes other things easier. Consider it similar to the "null object pattern" in programming; the empty version of an object is defined to exist and behave in a way which makes other stuff Just Work without needing to special-case anything.

  1. Computer programs can take each other as input; if you have a process which decides whether a program halts, you can write a program which feeds it to itself and then halts if and only if it doesn't halt. Basically creating the computer equivalent of "this sentence is false."

You must log in to comment.

in reply to @garak's post:

garak
@garak

The nomenclature is extra-confusing here: The paper claims an exact approximation for Chatin's Constant, which is not the same thing as calculating its exact value.

Do to the Halting Problem tomfoolery, calculating Chaitin's Constant has a second level of bullshit. If you have an algorithm that calculates digits of Chaitin's constant, and you've proven it correct, nonetheless if you run it and get N digits then the last few are incorrect. To actually find the first N digits, you need to run your already-proven algorithm for N+K digits, and then produce a second proof that there are no more than K wrong digits.

The phrase "Exact Approximation" in the title of the paper means they have produced the second proof. It's an approximation because it's only the first few digits (they claim 43), but it's an exact approximation because those digits have been verified to be true.

login to reply
gnar
@gnar

somewhat relatedly: the Busy Beaver game is in which one tries to describe the longest running Turing machine that eventually halts (it is not allowed to run forever). Usually, this is given with some size limitation (ex: the longest running Turing machine that eventually halts and has exactly N states) The number of steps that the winning Turing machine runs for is called the "nth busy beaver number", sometimes written as BB(n). As you might have guessed, it isn't possible to compute the Nth busy beaver number for arbitrary N (if you could, then you could pretty easily solve the halting problem: Simply run your Turing machine with N states for BB(N) steps. If it doesn't halt, then you know it has to run forever).

Hence, BB(n) is uncomputable for most values of n. It is also notable, that it grows incredibly quickly. Here's the first few values of BB(n):

BB(2) = 6
BB(3) = 21
BB(4) = 107
BB(5) = 47,176,870 (current best estimate)
BB(6) > 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10

In fact, since BB(n) is uncomputable, it must also grow faster than any computable function. It grows faster than any sequence of exponent towers and up-arrow-notation craziness that you can think of. It grows faster than the Ackermann Function or TREE(3) or pretty much anything else you can think of. If you want to win the biggest number game, just say "BB(1000000)" and you will probably win.

Another thing: we actually do have some upper bounds on which particular Busy Beaver numbers cannot be computed. There is a 7,918 state Turing machine which explicitly halts if and only if ZFC is inconsistent (famously, it is not possible to prove or disprove if ZFC is consistent from within ZFC--the statement is "independent of ZFC"). This implies that BB(7918)'s value is not computable--there is no way for us to ever find out it's value. This also raises other questions: what's the highest busy beaver number which we can compute? are there any problems that cannot be stated as a Turing machine smaller than 7918 states? Somewhere between BB(2) and BB(7918) is a point at which it is impossible to know which Turing machine runs the longest.

login to reply
garak
@garak

Yup, I wrote about busy beavers a little while ago too. That's some real shit. The independence from ZFC is just mind-boggling--although it also quickly makes sense! ZFC is an enumerable system, so you just build a turing machine that enumerates every true statement.

I think the values in your comment are the time complexity while my post uses the space complexity, just because it makes the first few numbers look more mundane.

login to reply
gnar
@gnar

ah right, usually busy beaver stuff is defined by the ones-written-to-tape or similar metric (but they're largely the same in terms of scale i think :P)

its also fun to try computing busy beaver numbers for simple languages like brainfuck--it turns out the problem is a bit more tractable there for larger programs, since its a bit harder to make complicated constructs in BF. still, it grows fast very quick (and arguably it's harder to detect for non-termination, but i have tried playing with it).

login to reply
radgeRayden
@radgeRayden

With Chaitin's Constant, you know how many will halt so you can simply wait for that many to halt and know the rest of them don't.

this seems like a basic misunderstanding of probability?

login to reply
Catfish-Man
@Catfish-Man

Not a mathematician but I think it's relying on the idea that in order for a member of a finite set (of Turing Machines) to have an N% probability of having a particular property, N% of the members of the set must have that property, so if you try all of them then the probability tells you all you need to know.

login to reply
grubby
@grubby

i was also confused by this, but wiki bailed me out: https://en.wikipedia.org/wiki/Chaitin%27s_constant#Relationship_to_the_halting_problem

highlight: "Knowing the first N bits of Ω, one could calculate the halting problem for all programs of a size up to N. Let the program p for which the halting problem is to be solved be N bits long. In dovetailing fashion, all programs of all lengths are run, until enough have halted to jointly contribute enough probability to match these first N bits. If the program p hasn't halted yet, then it never will, since its contribution to the halting probability would affect the first N bits. Thus, the halting problem would be solved for p."

i didn't find this totally satisfying but there is a more detailed explanation (via Chaitin) here: https://mathoverflow.net/a/177619

login to reply
grubby
@grubby

i don't follow this part of the argument tbh

"Omega_K will be less than omega because it is based on only a subset of all the programs that halt eventually, whereas omega is based on all such programs."

login to reply
grubby
@grubby

oh, i see what's going on here, it's some kinda Cantor set measure theory thing.

the "prefix-free" condition is important. if a string s is a valid program, then any longer string that begins with s is invalid.

the other important piece is the way that we calculate probabilities. it's not (halting programs of N bits / valid programs of N bits). it's instead a weighted sum where shorter strings contribute more than longer strings.

login to reply
garak
@garak

Exactly, those two facts combine to make this a valid probability.

The prefix-free property means that you can think of all of these programs as walking down a binary tree. Start with the empty string at the root: if your current string is a valid program you have a leaf, otherwise the left child is your current string with "0" at the end and the right child is your current string with "1" at the end.

Then the probability for any leaf (program) is the probability that a random walk down that tree, with a 50/50 chance each node to go left or right until you reach a leaf. This is exactly equivalent to a random process that concatenates binary digits one at a time until you get a valid program, but I find the tree makes it easier to visualize. Then the halting probability is just the sum of the probabilities of the leaf nodes/valid programs which halt.

Another way to think of the prefix-free property is that all strings are infinitely long, but once you reach a valid program any further digits are ignored. If you consider all infinite binary strings, the set of all such strings are exactly the real numbers in the unit interval (represented as binary). Then a valid finite program corresponds to the set of numbers which start with that prefix, which are an interval. And the probability for that program is the length of that interval.

This one-bit-at-a-time representation of programs is amenable to enumerating all valid programs, which is what lets you pull the "enumerate them all and run them all in parallel" stunt.

login to reply
garak
@garak

So what are your opinions on Bertrand Russell?

According to Wikipedia, Chaitin has made contributions to philosophy as well. But those seem to be mostly about the philosophical implications of his math work, and I can't tell if it's "real" philosophy or one of those cases where an expert in one field just tries to explain other fields to people in those fields.

login to reply
nullpat
@nullpat

tbh I think this part just activated the same reaction in me as roko's basilisk:

Knowing too many digits of this numbers would, in layman's terms, reveal the true name of god and end the world.

"isn't that just nerds reinventing religion?"

I've only read a little Bertrand Russell in a philosophy class, so I'm positively disposed to him but his actual work (at least the Principia) is pretty opaque to me.

Just from glancing at the wikipedia, Chaitin's other work does sound like it might be interesting and I'll probably see if I can get any of it from the library.

login to reply
upthorn
@upthorn

I'm confused!

Aren't the constraints "you must be able to represent each Turing Machine as a binary string" and "no such string can be the prefix of another such string" mutually exclusive in practice?

And if not, how the hell are they not?!

login to reply
xenofem
@xenofem

You can have an infinite number of binary strings where none is a prefix of another, for instance:

  • 1
  • 01
  • 001
  • 0001
  • ...

This on its own would work as an extremely inefficient way to represent all possible Turing machines - come up with some way to map Turing machines onto natural numbers, and the number of 0s is the number of your Turing machine. In practice there's much better representations available, but in general it's not hard to make these prefix-free.

login to reply
garak
@garak

The prefix-free property is equivalent to arranging all of the Turing Machines in a binary tree, with valid programs at the leaf nodes, and each string is a walk down that tree (0 means left, 1 means right, until you hit a leaf). Your construction is just the degenerate "always left" binary tree, which is totally valid and only impractical if you were going to actually use the damn thing, which we're not.

login to reply
upthorn
@upthorn

Right, okay, I was thinking of binary strings as binary numbers upon which an infinite number of 0s are implied to be prefixed (as well as postfixed after the radix point), rendering 1, 01, 001, ..., 0...01 all equivalent.

login to reply
Brisken
@Brisken

Mathematics is just Magic, I swear. Poorly understood by the masses, can be used to create wonders beyond human comprehension, can be abused by evil people to do heinous things, the most knowledgeable are slightly mad in some way. If someone could figure out how to write formulas in the air, we could probably cast fireballs too.

login to reply
Rhiannon
@Rhiannon

"Knowing too many digits of this numbers would, in layman's terms, reveal the true name of god and end the world." what do you mean by this? are we just talking about how the halting problem essentially leads to an incompleteness theorem, or

login to reply
garak
@garak

It is impossible to calculate (correctly?) digits after a certain point. Which means that the sequence of correct digits, were it to be known, is a demonstration that math is false.

There are a handful of objects like this is math, where if you were to successfully construct them then they demonstrate the system that constructed them is irredeemably flawed. For example, there are some sets that simply by being large enough, if you prove that they exist in ZFC then they disprove ZFC (by themselves being a proof of the consistency of ZFC).

This object in particular is a binary string, so it's natural to think of it as text. That's the best example of text I could come up with that has similar implications.

login to reply
Pinned Tags