BB(3, 3) is Hard • Hacker News Board

Re: BB(3, 3) is Hard

#61

Post by kevinventullo » Tue, Oct 17, 2023, 7:15 AM UTC

sligocki wrote: post #31

tybug wrote: post #21

I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it ha…

The issue is the "run the turing machine for BB(748) steps" part. We don't know what BB(748) is. If the god of busy beavers came to us and told us that value, then we could (in theory) run the TM that long and just like you say, that would prove whether ZFC is consistent. But in order for us mere mortals to compute BB(748) we would effectively need to figure out if this specific 748-state TM ever halted (along with a…

To put it another way, an oracle telling us an upper bound on BB(748) would be strictly more powerful than an oracle telling us ZFC is consistent.

Re: BB(3, 3) is Hard

#62

Post by auggierose » Tue, Oct 17, 2023, 7:24 AM UTC

acmiyaguchi wrote: post #59

jdthedisciple wrote: post #51

Earlier quoted context omitted.

This fits squarely into theoretical computer science. Going through any introductory TCS textbook will help you understand most of this stuff. CS students do this in their first or second year of their studies, and yes it's tough (at my uni this was among the most feared exams).

A first or second year (undergrad) student doing theoretical science to this level is astounding to me. It was an upper-division course for me, albeit a prerequisite for things like compilers and cryptography, so I'm sure it could be put earlier in the journey. Sipser's "Introduction to the Theory of Computation" was the book I had to read, and it certainly makes this post more accessible.

Interesting, Sipser starts the natural numbers with 1 in this book, instead of 0.

I like this choice, and I would like to use it myself. But if ℕ starts with 1, what do I call {0} ∪ ℕ? I guess ℕ₀ is a reasonable choice.

Re: BB(3, 3) is Hard

#63

Post by onetimeuse92304 » Tue, Oct 17, 2023, 7:46 AM UTC

thethimble wrote: post #60

onetimeuse92304 wrote: post #26

Earlier quoted context omitted.

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as effici…

But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?

Even if the universe is infinite, you can't use its infiniteness because you can't communicate partial results across infinite distances.

It is natural to think that the more time you have, the further you can travel to, potentially. But when it comes to the universe, the opposite is actually true. The more time passes, the less of the universe you can reach. A lot of universe you can see today is actually not at all reachable, meaning even if you shine the light back it will never reach the destination.

Re: BB(3, 3) is Hard

#64

Post by diogenes4 » Tue, Oct 17, 2023, 7:56 AM UTC

thethimble wrote: post #60

onetimeuse92304 wrote: post #26

Earlier quoted context omitted.

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as effici…

But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?

Spacetime (might be) infinitely large, but that doesn't imply that there is infinite matter or energy.

That said, this is kind of a dumb argument because far lower k values have lower BB(k) values already exceed the apparent information value of the universe at any given instant. Maybe there is infinite energy and matter, but that's also irrelevant if we can't perceive more than a finite subset of it.

Edit: well, i guess what would matter would be the information value of time, multiplied by enough bits to store the machine—I'm not sure i'm literate enough in the area to compute that. But, assuming that the heat death of the universe reaches a single (possibly compressed) end-state, it should still be finite—it's seeming quantized, anyway.

Re: BB(3, 3) is Hard

#65

Post by bmacho » Tue, Oct 17, 2023, 8:19 AM UTC

tybug wrote: post #28

Sniffnoy wrote: post #25

Earlier quoted context omitted.

> Of course, I'll now fall back on godel's second incompleteness theorem and say that one cannot prove, inside ZFC, that ZFC is consistent. But if the above turing machine halts, then we proved ZFC is consistent - a contradiction! No, the machine halts iff ZFC is inconsistent -- as you correctly stated up top. Somewhere along the way you got this reversed, looks like. There's the problem.

You're right, I misstated this - but I don't think this is fatal. The other sibling commenters pointed out the real issue with my thinking. The argument goes the same even though I misspoke here. If the machine {halts, runs forever} then ZFC is consistent. But this is a contradiction; so ZFC must be inconsistent. Tada, I have an inconsistency proof! That was the implied next step which made me think my logic was clea…

> You're right, I misstated this - but I don't think this is fatal.

It is crucial at this types of results, when you search for a proof.

There are a lot of things true, better make a table of it, instead of a wall of text:

  - If you observe the machine halting, ZFC is inconsistent. 
  - If the machine hasn't halted yet, you don't know if ZFC is consistent or not.

  - If ZFC is inconsistent, the machine will eventually halt. (You have an upper bound for this, given a contradiction.)
  - If ZFC is consistent, then the machine won't halt ever.

Also it is consistent with ZFC that this machine halts, since it is consistent with ZFC that ZFC has a contradiction. This means that if ZFC happens to be consistent, and you work in ZFC+contradiction, then you will know that your machine will eventually halt, yet it won't halt ever.

Re: BB(3, 3) is Hard

#66

Post by generic92034 » Tue, Oct 17, 2023, 8:27 AM UTC

tybug wrote: post #21

I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it ha…

It is funny to me that you are going for BB(748) in this context when you could go for the much, much, ... lower number BB(745), as outlined in [0].

[0]: https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

Re: BB(3, 3) is Hard

#67

Post by onetimeuse92304 » Tue, Oct 17, 2023, 8:37 AM UTC

diogenes4 wrote: post #64

thethimble wrote: post #60

Earlier quoted context omitted.

But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?

Spacetime (might be) infinitely large, but that doesn't imply that there is infinite matter or energy. That said, this is kind of a dumb argument because far lower k values have lower BB(k) values already exceed the apparent information value of the universe at any given instant. Maybe there is infinite energy and matter, but that's also irrelevant if we can't perceive more than a finite subset of it. Edit: well, i g…

It does not matter how much energy is there available in the Universe. Even if there is infinite amount of it, you can't still use it because only finite amount can ever be reached / affected by any single observer. Only finite amount of universe can ever reach any single observer.

So for example, there is a limit on the mass of the computer that can be constructed and still send its result to a single spot in space in the future. And the longer you wait, the smaller the limit because less and less of the universe is available to you to build the computer.

Re: BB(3, 3) is Hard

#68

Post by Sharlin » Tue, Oct 17, 2023, 9:02 AM UTC

onetimeuse92304 wrote: post #26

tybug wrote: post #21

I'm hoping someone can enlighten me here. My understanding is that there is a turing machine of 748 states [0], which halts iff ZFC is inconsistent (Thm 1). But this machine is a "physical" object, in the sense that we can materialize it on a computer and run it. Though we don't have the computing power for this currently, there is nothing in principle stopping us from running this machine for BB(748) steps: if it ha…

> This is not just some abstract result; this is a computation that we can perform and draw a real value from. No, this isn't a computation we can perform. There isn't enough energy in the visible Universe we can use to increase entropy to run this computation. Even if we built a computer that would use all matter and energy in the Universe, even if the computer only had one task and even if it ran the task as effici…

It doesn't matter whether we can physically do it, as long as we can mathematically do it. In math running a TM for an arbitrary, finite number of steps is not a problem. The actual answer to OP's question was given in one of the other subthreads, namely: the result tells us that BB(754) is not computable in ZFC. Some 754-state TMs halt, others run forever, but there is no way to figure out (without an oracle) which of them runs the longest while still eventually halting.

Re: BB(3, 3) is Hard

#69

Post by dullcrisp » Tue, Oct 17, 2023, 9:15 AM UTC

l33t7332273 wrote: post #56

meithecatte wrote: post #46

Earlier quoted context omitted.

How do you make the new machine compute BB(754)? BB is the canonical example of an uncomputable function, precisely because you can decide the halting problem if you can compute it (or any upper bound). Granted, BB may be computed for specific arguments, as OP mentions for 1–4, but the existence of the ZFC-dependent machine is, at least to me, a very good argument that the boundary of what's possible is much lower.

Oh, sure. I was just pointing out that the hardness is in determining the busy beaver number and that it didn’t matter if your algorithm halts iff ZFC is consistent or if it’s an algorithm that halts iff ZFC is inconsistent.

No, if you had an algorithm that (you could prove) halts iff ZFC is consistent, then if that algorithm halts, you’ll have a proof that ZFC is consistent, which isn’t possible. Thus, the existence of such an algorithm would be a contradiction that proves the inconsistency of ZFC.

The problem with your construction is that it relies on knowing the value of BB(754), which is impossible to know so long as ZFC is consistent, since its value is dependent on the consistency of ZFC.

Conversely, if ZFC is inconsistent, then there exists a (finite) proof of this fact, so the opposite case isn’t a problem.

Essentially it’s like saying define X to be the length of the shortest proof of the inconsistency of ZFC, if one exists. If I could prove any upper bound on X, I could prove the consistency of ZFC, which, according to Gödel’s incompleteness theorem, would itself prove the inconsistency of ZFC.

Re: BB(3, 3) is Hard

#70

Post by danbruc » Tue, Oct 17, 2023, 9:20 AM UTC

onetimeuse92304 wrote: post #63

thethimble wrote: post #60

Earlier quoted context omitted.

But if the universe is infinitely large then any finite thing should fit in it, right? Or are we saying that BB(748) can be infinite?

Even if the universe is infinite, you can't use its infiniteness because you can't communicate partial results across infinite distances. It is natural to think that the more time you have, the further you can travel to, potentially. But when it comes to the universe, the opposite is actually true. The more time passes, the less of the universe you can reach. A lot of universe you can see today is actually not at all…

Only because our universe is currently expanding, if it wasn't or would stop in the future, given enough time you could eventually distribute the task over a large enough region to perform the computation and afterwards combine the results in one place. And one would probably have to throw in a couple of technical requirements, for example that the energy density does not decrease faster than the future light cone expands.