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

Re: BB(3, 3) is Hard

#71

Post by thaumasiotes » Tue, Oct 17, 2023, 9:31 AM UTC

auggierose wrote: post #62

acmiyaguchi wrote: post #59

Earlier quoted context omitted.

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.

> I like this choice, and I would like to use it myself.

It's not a great choice, purely for the reason that there's already a convenient name for the positive integers, ℤ⁺.

Re: BB(3, 3) is Hard

#72

Post by FartyMcFarter » Tue, Oct 17, 2023, 9:31 AM UTC

jcagalawan wrote: post #52

joshxyz wrote: post #49

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.

Theory of Computation, Number Theory, and Probability are good starts.

You don't need any probability or number theory to understand busy-beavers even though the article mentions some probability stuff.

You also don't need them to understand the basic properties of Collatz problems.

So I'd reduce it to Theory of Computation and some extremely basic maths in order to have a reasonable basic understanding of the subject.

Re: BB(3, 3) is Hard

#73

Post by abetusk » Tue, Oct 17, 2023, 9:51 AM UTC

BB(3,3) is busy beaver (BB) problem, a subset of Turing machines (TM) [0], with 3 states (A,B,C) and three symbols (0,1,2) that can be written onto the infinitely long tape. An additional criteria for a Busy Beaver-like Turing machine is that there is a "halt" state, which can be seen in the article's table for state C reading input 0.

The table in the article (under "The Machine" section) describes the state on the left hand column (A,B,C) and the input on the top row (0,1,2). The entry in the table describes, as far as I can tell, what the Turing machine writes back to the tape, the direction it goes and the state it transitions to.

So for entry 'A', '2', the entry is '1LC', meaning it writes '1' at the tape position it's in, moves one to the left then transitions to state 'C'. State 'C' on reading symbol '0' will halt, as is the requirement for it being a buys beaver machine.

I very weakly understand the 'A(a,b,c)' notation in the 'Analysis' section but I don't quite understand what it's saying. The line that says "A(a,b,c) = 0^\inf 12^a 11^b The table below it describes what I believe are essentially reduction rules. That is, "if the state of the TM is like this, we can deduce it will be reduced to this state" which is how it relates back to the Collatz conjecture.

Anyway, nice article. Wish there was a "glossary" section that described the esoteric notation.

[0] https://en.wikipedia.org/wiki/Busy_beaver

[1] https://en.wikipedia.org/wiki/Turing_machine

Re: BB(3, 3) is Hard

#74

Post by FartyMcFarter » Tue, Oct 17, 2023, 10:05 AM UTC

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem

I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems?

BB(x, y) problems are trivially converted to the halting problem:

- find all machines with x states and y symbols that halt, set all the non-halting ones aside.

- run all the halting machines together one step at a time until they've all halted. The number of steps you've executed is the value of BB(x, y).

I believe Conway presented a reduction from the halting problem to collatz-like problems, so finding BB(x, y) for any value of x and y can be reduced to a collatz-like problem with this two step reduction (BB to halting problem to Collatz problem).

Re: BB(3, 3) is Hard

#75

Post by [deleted] » Tue, Oct 17, 2023, 10:07 AM UTC

FartyMcFarter wrote: post #74

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems? BB(x, y) problems are trivially converted to the halting problem: - find all machines with x states and y symbols that halt, set all the non-halting ones aside. - run all the h…

[deleted]

Re: BB(3, 3) is Hard

#76

Post by concordDance » Tue, Oct 17, 2023, 10:10 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…

> Though we don't have the computing power for this currently

I don't think you get how big BB748 is. To use a metaphor:

If you took stuffed the entire observable universe full of computronium that can do more calculations in a fragment the size of a human cell than our entire civilization, then shrank that universe down to the size of a grain of sand and filled our entire universe with that, THEN did this once for every possible distinguishable person (ie. If you can say after a lifetime of detailed observation that person A isn't identical to person B then they're distinguishable) you still aren't even close to BB748. In fact, I'd be surprised if you're over BB10 and you're definitely under BB20.

Re: BB(3, 3) is Hard

#77

Post by [deleted] » Tue, Oct 17, 2023, 10:14 AM UTC

auggierose wrote: post #62

acmiyaguchi wrote: post #59

Earlier quoted context omitted.

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.

[deleted]

Re: BB(3, 3) is Hard

#78

Post by dchftcs » Tue, Oct 17, 2023, 10:19 AM UTC

FartyMcFarter wrote: post #74

> Therefore, solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem I don't understand why this is surprising, in fact it seems trivially provable. Aren't all BB(x, y) problems reducible to Collatz-like problems? BB(x, y) problems are trivially converted to the halting problem: - find all machines with x states and y symbols that halt, set all the non-halting ones aside. - run all the h…

I think you got the direction reversed. Here you have a reduction of B(x,y) to the halting problem, which only shows that (a subset of) halting is at least as hard as B(x,y). You need a reduction from collatz to halting to B(x,y) instead. Collatz to halting is trivial, halting to B(x,y) seems a bit less so - you need to precisely define which subset of halting problems can be reduced from Collatz yet is no harder than B(3,3).

Re: BB(3, 3) is Hard

#79

Post by Xcelerate » Tue, Oct 17, 2023, 10:22 AM UTC

The halting problem often seems to “block” a lot of approaches to algorithmic information theory and induction that are based upon computable programs. However, is there any research on whether the halting problem actually has any sort of material influence on our ability to perform real-world induction?

For instance, if an oracle could tell us whether any given monotone universal Turing machine has reached a point in its execution where it will never print anything else to the output tape, would the results of induction using this oracle differ considerably from the case where we simply “skip” to the next program in an exhaustive search of program space after its fails to produce output for n consecutive steps (for sufficiently large n)? I’m referring to induction on cases that are not contrived as edge cases or adversarial examples (e.g., BB(3,3))—just induction on “regular” compressible data.

Re: BB(3, 3) is Hard

#80

Post by contravariant » Tue, Oct 17, 2023, 10:28 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…

A Turing machine which halts iff ZFC is consistent seems like it would be more interesting. In theory it would be possible to run it and show ZFC to be consistent that way.

Although I imagine it suffers from the problem that it can only be shown to work within ZFC or any theory powerful enough to prove the consistency of ZFC, which tells us nothing.