10 ms·
BB(3, 3) is Hard
- telegpt 3y ago[dead]
- haltist 3y agoPretty good writeup.
- throwawa14223 3y agoI appreciate the authors writing style. It helped me understand the subject without seeming verbose. That sweet spot can be difficult.
- sligocki 3y agoThank you! I'm so glad to hear!
- wodenokoto 3y agoIs this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
- noqc 3y agoIf BB is a computable function, then you can solve the halting problem by running every turing machine with n states for BB(n), and the ones that don't halt by then don't halt at all.
- gpm 3y agoSort 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 math problems that we know we can't prove or disprove). Incidentally Godel's second incompleteness theorem is that we can't ever prove we are in the first case. And then ya, BB being incomputable means that as BB grows at some point they start to be able to encode programs that halt if and only if a problem we can't prove or disprove is true. So we can't prove that program does or doesn't halt. Now, technically, proving/disproving something you can't prove or disprove would be proving false, which in turn could be used to "prove" every statement, and would therefore "encompass all maths", so what you said is in a sense correct. It's a threshold condition though, and one that kicks in well before you have turing machines large enough to encode "every" math problem. And in fact there is no finite number of states sufficient to encode every math problem (I can just make longer and longer strings of arithmetic for instance)...
- pjot 3y agoSo 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.
- gpm 3y agoThe collatz conjecture isn't a problem that we think is unsolvable, it probably (maybe even definitely?) has a solution. It is a problem that a lot of really good mathematicians have sunk a lot of time into and made basically no progress. Collectively the mathematical community has more or less decided that we don't know how to even approach solving this kind of problem yet, and probably won't be able to solve it in the foreseeable future. This article is saying that solving for BB(3, 3) requires solving a collatz-conjecture like problem, so it's probably also beyond our current abilities in mathematics. It's not saying it's unsolvable, just that we probably won't figure out the solution anytime soon. As for why solving BB(3, 3) matters... it doesn't really. It's just an intellectual curiosity. We've figured out some busy beaver numbers. We've proven some upper bounds on the biggest ones we can figure out, but there's a big gap between what we've solved and what we've shown we can't solve for. Making that gap smaller is something of a game.
- pjot 3y agoGot it. Thanks for adding context!
- sligocki 3y agoThe 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 :)
- kmeisthax 3y agoSort 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 are true or false, so anything that wants to solve the halting problem or solve BB has to be able to know all maths[0]. Of course, this is possible because Turing-completeness is the boundary of computability. Anything that can have a computer in it is itself a computer. [0] This isn't actually the thing that makes halting undecidable. Undecidability comes from programs that "pull themselves into the halting problem" by only halting if a hypothetical halting problem decider would claim that they don't halt.
- penteract 3y ago> 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_halting_problems https://en.wikipedia.org/wiki/Oracle_machine#Oracles_and_hal...
- luc4 3y ago> Uncomputable functions exist because the halting problem exists. Uncomputable functions exist because there are only countably many Turing machines. There are problems that stay uncomputable even if the halting problem were computable.
- deleted 3y ago[deleted]
- CJefferson 3y agoGreatly 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.
- nine_k 3y agoNot "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.
- parentheses 3y agoI have always been curious about BB but never saw Scott Aaronson's survey of the topic. Link within.
- sligocki 3y agoHis survey 3 years ago has kicked off quite a flurry of Busy Beaver activity of which my entire blog and https://bbchallenge.org/ https://bbchallenge.org/ are a couple examples.
- diziet 3y agoRelated: https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.html https://nickdrozd.github.io/2020/08/13/beeping-busy-beavers.... and https://googology.fandom.com/wiki/Googology_Wiki https://googology.fandom.com/wiki/Googology_Wiki
- philip-b 3y ago`1RB2RA1LC_2LC1RB2RB_---2LA1LA` - how do I read this?
- twiceaday 3y agoIt is a state transition table, the expansion is featured in the article right under it, or here https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA For example: If in state B and the tape at the current marker reads 0: write 2, move the head Left once, and go to state C.
- gpm 3y agoClick on the link in the article [0] and you'll get a page that expands it to a human readable table. Each current (state, tape value) pair maps to a (new tape value, direction to move tape head, new tape value) triple. [0] https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
- progbits 3y agoThere is a more readable state table but each underscore separates a group of transitions for one symbol, writen as groups of 3 characters for each symbol. These are the symbol to write, new state and direction to move. The --- state halts.
- nneonneo 3y agoProbably 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 (as with the classic Collatz problem).
- sligocki 3y agoYeah, 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 :)
- FartyMcFarter 3y ago> "Solving the BB(3, 3) problem is at least as hard as solving this Collatz-like problem." > How hard is this Collatz-like problem? Well, let's see if anyone can solve it :) I thought John Conway already proved that all instances of the halting problem can be converted to a Collatz-like problem [1]. So one could say this about all BB values, not just BB(3, 3). Some will be easy, some will be hard, but all are reducible to Collatz-like problems IIUC. [1] https://julienmalka.me/collatz.pdf https://julienmalka.me/collatz.pdf
- 3y ago
- tybug 3y agoI'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 halts, we have proven by Thm 1 that ZFC is inconsistent. If not, we have similarly proven that ZFC is consistent. I want to stress that this is key to my confusion. This is not just some abstract result; this is a computation that we can perform and draw a real value from. 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! Where is the mistake here? My current guess is there is a technical detail in the proof of Thm 1 which uses a stronger metatheory than ZFC to show that the 758-state turing machine halts iff ZFC is inconsistent. This is not a contradiction, because yes, we can run the turing machine for BB(748) steps, but that will only show that ZFC+ proves ZFC is consistent, which is already well known - ZFC + there exists an inaccessible cardinal does the job. However, I haven't looked at the paper in detail to know whether this is the case. Does anybody who has thought deeply about this problem have insight to offer? [0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...
- Pannoniae 3y agoThe only problem is that proving it halts is "easy" - run the program, wait a few million years, it halts. Yey. Proving it doesn't halt is much harder, since you can run it for TREE(3) steps if you want, that's still not proof it won't halt in TREE(3)+1 steps. So in a way, it's not possible to "just run it", sadly.
- hakuseki 3y ago> there is nothing in principle stopping us from running this machine for BB(748) steps How would we compute the value of BB(748)?
- nine_k 3y ago
- joshxyz 3y agoThis 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.
- jdthedisciple 3y agoThis 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).
- acmiyaguchi 3y agoA 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.
- auggierose 3y agoInteresting, 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.
- thaumasiotes 3y ago> 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, ℤ⁺.
- auggierose 3y ago
- abetusk 3y agoBB(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 <A 11^c 0^\inf" is describing the input tape state, with s^x denoting symbol s repeated x times, but I don't quite understand what the "<A" is. 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 https://en.wikipedia.org/wiki/Busy_beaver [1] https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/Turing_machine
- deleted 3y ago[deleted]
- konstantinua00 3y ago> 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. Technically, that's "halt" _transition_. There's supposed to be an implied Halt state - but it's straight up easier to treat halting as smth like "invalid instruction" hardware exception. > The line that says "A(a,b,c) = 0^\inf 12^a 11^b <A 11^c 0^\inf" is describing the input tape state While yes, it can be an input - instead it is mostly treated as "intermediate" state of the tape. TM is quite low level, so various abstractions are welcome. If you can prove that input you're interested in (empty tape) gets to your abstraction and stays there - stuff gets simpler. > but I don't quite understand what the "<A" is. One of very useful abstractions without much cost is to keep track of direction head was travelling in. 1) instead of "head is on this cell and state kept outside" it allows inline notation, while visually pointing to the cell the head is on 2) it's mostly explained as representation of TM with 2 stacks which is easy to implement and run 3) direction is already encoded in the transitions "1LC == <C 1" That allows nice rewrite rules like "B> 1 -> 1 B>" that simplify manual playthrough, and it works nice with intuition - e.g. B> keeps going right all the way until it encounters 0, like a ship with a pointy nose through the water. And, well, additional state helps a lot of the time.
- FartyMcFarter 3y ago> 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).
- deleted 3y ago[deleted]
- dchftcs 3y agoI 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).
- deleted 3y ago[deleted]
- FartyMcFarter 3y agoMy understanding is that this blog post converts a specific instance of the halting problem into a Collatz-like problem. It starts with a description of a specific Turing machine, and presents a Collatz-like problem that, if solved, also answers whether that Turing machine halts or not. Isn't this almost exactly what Conway did, with the only difference being that Conway's proof works for all Turing machines, and this proof only works for a specific Turing machine?
- Xcelerate 3y agoThe 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.
- deleted 3y ago[deleted]
- cubefox 3y agoI'm not sure this is what you mean but obviously in practice uncomputable problems don't differ from problems which are perfectly computable in theory but far too slow to be computed in practice.
- SCHiM 3y agoI'm a not educated in mathematics, so I can't know for sure if what I'm going to respond to your question is really relevant or not. But here it goes anyway. I'm a security researcher, and I write my own fuzzers. Fuzzers are tools that automatically search for inputs that have security implications for the program that you're testing. They algorithmically generate and mutate inputs, feed them to a program, and observe what happens, tens/hundreds/thousands of times a second. If an input crashes a program you can think of this as "halting" the program. To have a fuzzer that could find any or all bugs in any program you run it on, in a feasible amount of time, would surely involve solving the halting problem I think. And sure, even after billions of tests, people still manage to find bugs in image decoders, so the fuzzers we do have are not flawless. At the same time, I have experienced in the real world that fuzzers manage to penetrate unexpectedly deep into complex programs if given enough time. The validation on input performed by the target under test, the limited memory and storage in a modern PC sort of helps to keep your fuzzer on the rails. Unless cryptography is involved, which are like computational tar-pits for fuzzers. Any well guarded/specified program acts as its own guardrail against needing to solve the halting problem for the fuzzer. It convinced me of the following, regarding the finding of security bugs in programs: 1) Fuzzers are good at targeting programs that perform rigorous input validation, barring cryptography. 2) You don't need a fuzzer for a program that does not perform rigorous input validation (where the fuzzer doesn't necessarily work well.)
- kzrdude 3y agoIs there any intution for why BBB (beeping busy beavers) can run for much longer (before quasihalting?) One thing I see is that they effectively don't need to use a halt state. So maybe a 3-state BBB is sort of similar to a 4-state BB in that sense. What is there more to it?
- voidmain 3y agoA program can only halt once, but can beep any number of times. So you can make a size X program (or turing machine) that simulates running every program (or turing machine) up to some size Y >> X, and whenever any of those programs halts it beeps. The last time it beeps will be when it simulates the halting of BB(Y) after more than BB(Y) steps, so BBB(X) > BB(Y) >> BB(X). IIRC basically this same construction means that while knowing BB(N) lets you (very slowly) compute the halting problem for programs up to size N, knowing BBB(N) lets you (even more slowly) compute the halting problem for turing machines supplied with a halting oracle up to that size.