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

31–40 of 146 posts

Re: BB(3, 3) is Hard

#31

Post by sligocki »

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 all the other 748-state TMs).

Re: BB(3, 3) is Hard

#32

Post by [deleted] »

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…

[deleted]

Re: BB(3, 3) is Hard

#33

Post by dandanua »

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.

Re: BB(3, 3) is Hard

#34

Post by nine_k »

CJefferson wrote: post #18
wodenokoto wrote: post #5

Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?

Greatly simplifying, the most important result in comparability is “the halting problem”, which means we have no way of telling, for any program, if given some input it will halt or run forever. After that, it’s not surprising there is some BB we can’t solve, and it’s interesting to investigate which we can, and can’t, solve.

Not "for any program", but "for an arbitrary program".

We can trivially prove that a program that always goes to the next step, without branching, always terminates. With more effort we can prove termination of certain segments with conditional jumps, certain forms of recursion and loops, etc. This is not purely theoretic: e.g. EBPF programs in the Linux kernel are only admitted if the kernel can prove that they terminahe.

What we can't do is to prove it in an arbitrary case, without putting limits on the program's structure.

Re: BB(3, 3) is Hard

#35

Post by sligocki »

nneonneo wrote: post #20

Probably more accurate to say that BB(3, 3) looks hard; that is, it encodes a Collatz-type problem, and many Collatz-type problems are very hard to solve (including, of course, the classic Collatz conjecture). However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (a…

Yeah, I've oversimplified a bit with this title. The more accurate statement is in the first paragraph of the article: "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem."

I also agree somewhat on the one trajectory vs. multiple trajectories point. However, note that (assuming we live in the world where this TM never halts) proving a single trajectory in this system is "harder" than a single trajectory in the classic Collatz conjecture. Specifically, (assuming the Collatz conjecture is true) proving any single trajectory is "simply" a finite computation. However, proving a single trajectory from the article requires showing that it never halts which will require some more fancy math!

Anywho, I don't want to oversell it. This does not prove that BB(3, 3) requires proving the Collatz conjecture or any existing well-studied open problem in Math. But I think it's sort of a "second best" result: As hard a problem akin to a well studied problem.

How hard is this Collatz-like problem? Well, let's see if anyone can solve it :)

Re: BB(3, 3) is Hard

#36

Post by drpixie »

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.

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

Re: BB(3, 3) is Hard

#39

Post by penteract »

kmeisthax wrote: post #9
wodenokoto wrote: post #5

Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?

Sort of . Uncomputable functions exist because the halting problem exists. So any function whose definition includes anything to do with halting also becomes uncomputable. e.g. BB is uncomputable because you have to determine all the TMs that would halt given n and m. The entire rest of mathematics is smuggled into BB via the halting problem: you can write programs that only halt if arbitrary mathematical conjectures…

> you can write programs that only halt if arbitrary mathematical conjectures are true or false

I don't think this is quite right - you can write programs that halt iff arbitrary mathematical conjectures are provable (in a suitable system of logic/axioms such as ZFC), but there are problems (such as questions about Turing machines with a halting problem oracle[0]) for which we can't straightforwardly construct a program which halts iff they are true.

[0] https://en.wikipedia.org/wiki/Oracle_machine#Oracles_and_hal...

Re: BB(3, 3) is Hard

#40

Post by tux3 »

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…

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 inconsistent, without using BB. If you keep trying forever and never find one, you'll never be able to conclude anything at any point, just like with watching the machine run

Post reply on HN