Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BB(3, 3) is Hard

sligocki.com

Post reply on HN
Print view View original

41–50 of 146 posts

Re: BB(3, 3) is Hard

#41

Post by sligocki »

pjot wrote: post #12
gpm wrote: post #7

Earlier quoted context omitted.

Sort of. There are math problems that we "know" we can't prove or disprove, unless we can prove every statement both true and false (this is Godel's first incompleteness theorem). If we can prove every statement both true and false then our proof system just sucks and proving something means nothing so we should choose another proof system where that's not the case, so we assume we're in the first case (there are mat…

So is this (BB) then just an exercise demonstrating our inability to reasonably solve the problem? I suppose what I’m asking is what is its significance? Or why does this matter? As a self taught programmer, I realize I have definite gaps in the more theoretical realms of computer science.

The Busy Beaver problem sits somewhere on the range from "intellectual curiosity" to "lens that allows us to view the edges of uncomputability". I would guess that the majority of people doing work here are hobbyists (including myself). In fact, when Tibor Rado first introduced BB, he introduced it as the "Busy Beaver Game", so it has had a playful energy since the beginning :)

Re: BB(3, 3) is Hard

#42

Post by l33t7332273 »

Sniffnoy wrote: post #25
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…

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

I don’t think that’s it. I think it’s easy to take such a machine and make a new one that halts iff ZFC is consistent.

Call the machine that halts iff ZFC is inconsistent A. Now consider the machine which computes the following algorithm:

Run A BB(754) times. If A halts, then run forever, else halt.

If A halts then our machine runs forever, and vice versa. Thus, our machine halts when ZFC is consistent and our machine runs forever when A halts, so ZFC is consistent iff our machine halts.

“Halts” doesn’t seem like a real word after writing that.

Re: BB(3, 3) is Hard

#43

Post by l33t7332273 »

tux3 wrote: post #40
tybug wrote: post #28

Earlier quoted context omitted.

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…

It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC incons…

> If it runs forever (likely), then you will never be able to say anything about ZFC.

But if you run it for BB(754) many steps, you will know.

Re: BB(3, 3) is Hard

#44

Post by modeless »

dandanua wrote: post #33
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…

> if it halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. The second part is wrong. We can't physically check that a program runs forever - this requires an infinite amount of time.

His point is if you know the value of BB(748) then you don't have to wait forever, just BB(748) steps, as after that the Turing machine is guaranteed not to halt. The problem with his argument is that we don't know the value of BB(748). Not only that, it is incomputable, which resolves the contradiction.

Re: BB(3, 3) is Hard

#45

Post by meithecatte »

nine_k wrote: post #29
hakuseki wrote: post #23

Earlier quoted context omitted.

> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?

Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.

Do note that any function f(n) that is always (or even just eventually always) greater than BB(n), is uncomputable, for very similar reasons.

Re: BB(3, 3) is Hard

#46

Post by meithecatte »

l33t7332273 wrote: post #42
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.

I don’t think that’s it. I think it’s easy to take such a machine and make a new one that halts iff ZFC is consistent. Call the machine that halts iff ZFC is inconsistent A. Now consider the machine which computes the following algorithm: Run A BB(754) times. If A halts, then run forever, else halt. If A halts then our machine runs forever, and vice versa. Thus, our machine halts when ZFC is consistent and our machin…

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.

Re: BB(3, 3) is Hard

#47

Post by tux3 »

l33t7332273 wrote: post #43
tux3 wrote: post #40

Earlier quoted context omitted.

It's simpler than this still. If it runs forever (likely), then you will never be able to say anything about ZFC. If you see it halt, ZFC is inconsistent. If you never see it halt, you CAN'T conclude anything. But we could already do that under Gödel incompleteness, so there's nothing unusual there! If you write down random proofs on paper and find a correct proof that leads to contradiction, you've proved ZFC incons…

> If it runs forever (likely), then you will never be able to say anything about ZFC. But if you run it for BB(754) many steps, you will know.

Yep. But I think it's easy to show that this is circular, since you can't know BB(754) without knowing whether it runs forever.

And you can't prove that it'll run forever without seeing it go past BB(754) and still keep going

BB(754) is X if ZFC is consistent, Y otherwise

Since you can't prove that ZFC is consistent (only disprove), you can't know BB(754), which is the thing we were trying to use to determine whether ZFC is consistent in the first place!

The definition doesn't make it obvious, but this is just the same as plain Gödel incompleteness, we can't get any extra info about ZFC even in principle (unless we happen to see it halt, by chance)

Re: BB(3, 3) is Hard

#48

Post by dllthomas »

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…

We don't need to know BB(748), just an upper bound on BB(748).

... which means we can't prove any upper bound on BB(748) within ZFC.

Re: BB(3, 3) is Hard

#49

Post by joshxyz »

This is too much nerd for me.

Can anyone tell me what is the required pre-requisite of knowledge to understand things like this? Like will knowing basic calculus be enough? What specific topics or subjects will give me good fundamentals on these things?

Thank you.

Re: BB(3, 3) is Hard

#50

Post by dllthomas »

drpixie wrote: post #36
nine_k wrote: post #29

Earlier quoted context omitted.

Computing BB(748) would be best, but if we could get an upper-bound estimate that's reasonably close, that would suffice.

Reaching a "reasonably close" upper bound estimate wouldn't provide proof ... probability maybe, but not proof.

If we've proved that a number is an upper bound on BB(748), then running for that many steps without halting means it has also run BB(748) steps without halting.
Post reply on HN