8 ms·
BB(3, 4) > Ack(14)
- VagabundoP 2y ago[flagged]
- computerphage 2y agoAnd you thought your for-loops were too deeply nested!
- deleted 2y ago[deleted]
- supriyo-biswas 2y agoCan someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?
- frutiger 2y agoEach row is a state and each column is the symbol that was just read off the tape. So the first row & first column mean "I have just read symbol 0 and am currently in state A". The cell in the table describes which actions to perform. The first row & first column has "1RB" which means: "replace the symbol on the tape with '1', shift 1 symbol to the right on the tape and switch to state 'B'". The state 'Z' corresponds to the halting state.
- treyd 2y agoEach triplet seems to be the symbol to write, and direction to move in, and the next state. You can think of the behavior of a turing machine as a function of the current state and the symbol read that's repeated iteratively.
- LegionMammal978 2y agoThere's a brief explanation at [0]. (Note that "1RZ" is understood to be a halting transition, since state "Z" has no rules.) Wikipedia also has a more elaborated example of a TM state table [1]. You can see the trace of this particular TM at [2]. [0] https://bbchallenge.org/story#turing-machines https://bbchallenge.org/story#turing-machines [1] https://en.wikipedia.org/wiki/Turing_machine#Formal_definition https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti... [2] https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2...
- deleted 2y ago[deleted]
- nickdrozd 2y agoThe "states" (A, B, C) correspond to goto targets. The "colors" (0, 1, 2, 3) are runtime data. At each state, the current color is read, and an instruction is executed (print some color, move left or right, goto some state) based on which color is there. Transliterated into C it looks like this: #include "machine.h" int main(void) { A: switch (SCAN) { case 0: WRITE(1); RIGHT; goto B; case 1: WRITE(3); LEFT; goto B; case 2: WRITE(1); RIGHT; goto H; case 3: WRITE(2); RIGHT; goto A; } B: switch (SCAN) { case 0: WRITE(2); LEFT; goto C; case 1: WRITE(3); RIGHT; goto B; case 2: WRITE(1); LEFT; goto C; case 3: WRITE(2); RIGHT; goto A; } C: switch (SCAN) { case 0: WRITE(3); RIGHT; goto B; case 1: WRITE(1); LEFT; goto B; case 2: WRITE(3); LEFT; goto C; case 3: WRITE(2); RIGHT; goto C; } H: HALT; } Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations?
- sans-seraph 2y ago> Question: are there any opportunities to rewrite this logic in a more "structured" style, or to make any other optimizations? Because A and C only jump to B it is possible to structure this using only loops and one boolean. Let us use Rust to demonstrate as it lacks GOTO: let mut a = true; loop { loop { if a { // state A match scan() { 0 => { write(1); right(); break } 1 => { write(3); left(); break } 2 => { write(1); right(); return } 3 => { write(2); right() } } } else { // state C match scan() { 0 => { write(3); right(); break } 1 => { write(1); left(); break } 2 => { write(3); left() } 3 => { write(2); right() } } } } a = loop { // state B match scan() { 0 => { write(2); left(); break false } 1 => { write(3); right() } 2 => { write(1); left(); break false } 3 => { write(2); right(); break true } } } } Of course it is possible to rewrite this as a single loop if you are willing to accept two bits of extra state rather than one.
- sw1sh 2y agoI've made a small repository with current record holders that also shows examples of running these machines with Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/ https://datarepository.wolframcloud.com/resources/The-Busy-B.... I guess I also need to update it now.
- carapace 2y agoIn Python: def L(): global index, tape if index: index -= 1 else: tape.insert(0, 0) def R(): global index, tape index += 1 if index >= len(tape): tape.append(0) table = { ('A', 0): (1, R, 'B'), ('A', 1): (3, L, 'B'), ('A', 2): (1, R, 'Z'), ('A', 3): (2, R, 'A'), ('B', 0): (2, L, 'C'), ('B', 1): (3, R, 'B'), ('B', 2): (1, L, 'C'), ('B', 3): (2, R, 'A'), ('C', 0): (3, R, 'B'), ('C', 1): (1, L, 'B'), ('C', 2): (3, L, 'C'), ('C', 3): (2, R, 'C'), } state = 'A' tape = [0] index = 0 while state != 'Z': tape[index], direction, state = table[state, tape[index]] direction()
- wwalexander 2y agoI found this quite helpful: https://nickdrozd.github.io/2020/10/04/turing-machine-notation-and-normal-form.html https://nickdrozd.github.io/2020/10/04/turing-machine-notati... Despite a CS undergrad I don’t recall really learning any of these canonical representations of TMs before.
- deleted 2y ago[deleted]
- immibis 2y agoDiscord links! As citations for major results in foundational computer science!
- Analemma_ 2y agoI understand the complaint here, but a lot of recent impressive progress in mathematics has been by rapid collaboration + iteration (e.g. the project to improve Zhang's prime gap bound), and it may be the case that different communication tools are not easily fungible with Discord in this regard. You have to go where the people actually are.
- wizzwizz4 2y agoBut Discord isn't citable. Somebody needs to archive the Discord and make that available through the proper channels (e.g. a website, a book, the Internet Archive).
- univerz 2y agothat post was just an (work in progress) update. Shawn's blog post is a proper announcement - much better than i would have written :)
- lambdaxyzw 2y agoWell it was cited so by definition it's citable. I don't like discord but... The people doing research have chosen this method of collaboration. I like their research. Let's not be choosing beggars and tell them how to conduct their research.
- Almondsetat 2y agoBut papers aren't citable. Somebody needs to archive the paper and make it available through the proper channels (e.g. a website, library, journal, the Internet Archive).
- kryptiskt 2y agoThere are a ton of "personal communication" cites out there that are dead ends. The point of the cite isn't to provide a handy link, though it's nice if it is one, but to hand the credit where the credit is due.
- tromp 2y agoThe new BB(3,4) record holder is 0 1 2 3 A 1RB 3LB 1RZ 2RA B 2LC 3RB 1LC 2RA C 3RB 1LB 3LC 2RC with the triple (t',d, s') in row s column t specifying the transition from state s with symbol t under the tape head. the machine overwrites symbol t with t', moves the tape Left/Right according to direction d, and changes state from s to s', halting if s'==Z. This is 3*4*log2(4*2*log2(4+1)) or about 64 bits of information. Meanwhile, in only 49 bits, BBλ(49) far exceeds Graham's number [1]. [1] https://oeis.org/A333479 https://oeis.org/A333479
- nilstycho 2y agoCan you help me understand the log2(4+1) term? I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51. I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60. Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?
- tromp 2y agoI miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.
- im3w1l 2y agoYou also need to subtract some bits from symmetries right? Like you can mirror the tape. You can relabel states B and C. And you can relabel symbols 1, 2, 3. Though the analysis is complicated a little bit by the fact that some (combinations) of those operations may yield the exact same machine.
- nilstycho 2y agoAlso, is there any sense in restricting the universe of machines to those that include one and only one halting symbol? Machines with more or fewer than one halting symbol are possible, but they're less interesting, right?
- 2y ago
- PatronBernard 2y agoNice that the author provides some context...
- nickdrozd 2y agoIt is sometimes thought that extremely long-running Turing machine programs must be deeply complicated, or "spaghetti code". This new reigning champion program is a counterexample. All things considered, it is relatively simple. There are three states: A, B, C. (States are just like goto targets in C.) State B passes control to A and C, but states A and C don't "know about" each other; they only pass control back to B. This is a sort of modular construction, whereas in true spaghetti code each state would be able to pass to all the others. This program has some other interesting features. It never prints a blank (that is, whenever it scans a 0, it prints 1, 2, or 3). Additionally, every instruction changes either the state or the color -- there are no "lazy instructions" like B1 -> 1LB that just move position without changing anything else.
- LegionMammal978 2y agoThere is some debate in the bbchallenge project regarding the current long-running champions: do their properties reflect those of the actual longest-running machine of that size, or are their properties just the easiest to automatically search for and prove things about, as a kind of streetlamp effect? There's no way to know, until the entire search space has been ruled out, either definitely or heuristically. (Every size past BB(5, 2) contains chaotic, pseudorandom machines that are expected to run forever, but can't be proven to do so without big advances in number theory.) Though I suspect that no long-running machine can be utterly chaotic, at least when you look at the patterns it produces on the tape. To run for a long time, a machine must simulate some sort of higher-level rule: if it were dumping symbols on the tape at random, then it would very soon reach a halting configuration, a cyclical configuration, or some other simplified pattern. Still, one can have long-running machines that do simulate something chaotic on a higher level, spending an inordinate amount of time between each high-level step until it halts.
- kevinventullo 2y agoAt a high level, wouldn’t you expect Champions to be chaotic in the limit? As in, the halting problem tells us that any increasing sequence of Champions is not computable.
- mikewarot 2y agoThis all sounds like extreme Code Golf to me. Here's a tangent to explore: A BitGrid[1] (my personal hobby horse) only has 4 bits of state per cell, so a 4x4 grid of cells can't count more than 2^64, no matter what. Finding the highest it could count would be interesting. For small grids, the edge connections would dominate the outcome. [1] https://esolangs.org/wiki/Bitgrid https://esolangs.org/wiki/Bitgrid [2] https://github.com/mikewarot/Bitgrid https://github.com/mikewarot/Bitgrid
- ziofill 2y agoThere are only so many Turing machines that we can possibly describe with a not too large amount of symbols such as 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC. The fact that some of these can make such a crazy large number of steps before halting to me is mind blowing.
- kingofthecob 2y agoIf you know, you know I guess. I certainly have no idea.
- __MatrixMan__ 2y agoThe acronyms refer to: https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Ackermann_function https://en.wikipedia.org/wiki/Ackermann_function As I understand it, the game around functions like this is to get as close to infinity as you can, but not quite, and then to try to uncover properties about what you find there. I'm under the impression that it's a certain kind of fun because the results are all way too large to work with computationally, so rather than comparing the values (which you can't calculate directly) you have to reason about the various algorithms that yield them. That's all I got. The gust of the post is greek to me. I wish I had more computer science and less software engineering under my belt. Then maybe this could be my kind of fun too.
- LegionMammal978 2y agoWell, the goal is to get as close to infinity as possible with the smallest program possible. We can name big numbers just fine, by recursing over recursion for some number of steps, but the fun part is to have these fall out 'naturally' from the space of small Turing machines. In this case, we can actually name the number of symbols in terms of Knuth's up-arrow notation [0], which describes the sequence of operations starting with multiplication, exponentiation, repeated exponentiation (called tetration, e.g., 2↑↑5 = 2^[2^[2^[2^2]]]), repeated tetration (called pentation, e.g., 2↑↑↑5 = 2↑↑[2↑↑[2↑↑[2↑↑2]]]), and so on. This number is big enough that it needs 15 arrows in a row to describe it reasonably. So it's not just that the number is very large, it's that we can also put a neat lid over its value. For instance, we know it's still nothing compared to Graham's number, which can't be described with any reasonable number of up-arrows. [0] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
- casercaramel144 2y agoI was curious as to how it works, so I implemented here: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc If you run it for a bit you see what's going on, State B turns 0's into 2's and 1's into 1's transitioning to C and state C turns 3 -> 2's and transitions to A. So you just iteratively lengthen your run of 3's exponentially since it requires a full pass through all the 3's to fix a 2->1.
- tux3 2y agoIt's fairly easy to make a turing machine that goes exponential and blows up forever. But the really tricky part to understand is why it eventually stops. After an unimaginably high number of steps.
- deleted 2y ago[deleted]
- fsmv 2y agoIs it not true that BB(5) > BB(3,4)? On the https://bbchallenge.org https://bbchallenge.org site it said they're trying to prove or disprove the conjecture that BB(5) is about 47 million but BB(3,4) is apparently much bigger than that.
- sligocki 2y agoYes, it seems that BB(3, 4) >>> BB(5, 2) (BB(5) = BB(5, 2)). This is not too surprising since BB(3, 4) has 12 transitions in it's table (3*4), while BB(5, 2) only has 10. But it seems that also BB(3, 4) >> BB(6, 2) (which both have the same number of transitions, so it appears that having more symbols is valuable to these little TMs.
- tgv 2y agoI think I can explain that. If you only have two symbols, you can encode the same information as having four symbols in two cells, so performing the same operation on them requires an extra state to read the first of the two and then move to one of two other states to handle the second. Less symbols requires more states. This is related to the linear speed-up theorem, which roughly states that you can speed up any TM by expanding its alphabet. And speed-up is not what BB is about. So actually, it would make sense to limit the the busy beavers to BB(n, 2) only.
- ks2048 2y agoI don’t know why, but these probably-useless-results (which frankly I don’t 100% understand) intrigue me more than the incredibly-useful LLM advances. I guess because I’m naturally drawn to “simple” mathematical truths more than “messy” engineering results.
- koromak 2y agoCan someone give a quick description of why this one is special? I'm familiar with turing machines (sort of), but I can't deduce why this specific instruction set is impressive. Whats an Ackerman-level function? Whats it actually computing?
- earthboundkid 2y agohttps://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html