I 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.
BB(3, 4) > Ack(14)
91–100 of 114 posts
Re: BB(3, 4) > Ack(14)
#92The 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…
Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm ( https://nickdrozd.git…
Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? Just watching the machine run, I would guess at some kind of infinite behavior. It is remarkable that this is not the case.
Re: BB(3, 4) > Ack(14)
#93Earlier quoted context omitted.
The "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; c…
I love these puzzles. GNU C supports a label as value for computed goto. This is useful for direct threaded dispatch. You trade off a branch instruction for an address lookup, but it makes the code more structured. int main(void) { void* A[] = {&&A0, &&A1, &&A2, &&A3}; void* B[] = {&&B0, &&B1, &&B2, &&B3}; void* C[] = {&&C0, &&C1, &&C2, &&C3}; goto *A[SCAN]; A0: WRITE(1); RIGHT; goto *B[SCAN]; A1: WRITE(3); LEFT ; go…
> GNU C supports a label as value for computed goto.
Why doesn't any modern C standard like C23 include this? Seems like a glaring omission.
Re: BB(3, 4) > Ack(14)
#94Earlier quoted context omitted.
Because Discord is a proprietary glorified IRC SaaS; its contents are, by nature, ephemeral and under control of the vendor. I'd expect such links to rot very quickly. Collaborating on Discord is fine. Important results, including citations backing them, should really be published or at least replicated in more durable medium that's less susceptible to link rot, and easier to archive. Today, that's PDFs in paper repo…
I don't see any reason why the original publication venue has to end up being the canonical reference. That's not even true for traditional peer-reviewed papers. Have you ever seen an original physical copy of, say, Einstein's annus mirabilis papers? I haven't. I suspect that these are extremely rare and valuable collectors items and only trained archivists are even allowed to handle them. The right way to reference…
> Have you ever seen an original physical copy of, say, Einstein's annus mirabilis papers
I was a grad student at the institute for theoretical physics in Heidelberg. It's famously housed in two old villas with little room for books, so all the walls in almost all rooms are lined with shelfs. In the office I shared with five other students, there was one shelf in it that was locked. The only one in the building. In it was one book from 1905 that had a different color than all the others.
That's the physical copy of the papers you mean. They had issues with theft so they had to have it replaced and then lock it. It probably wasn't even original though.
Re: BB(3, 4) > Ack(14)
#95Can 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?
The "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; c…
What's the initial state supposed to be?
Re: BB(3, 4) > Ack(14)
#96Earlier quoted context omitted.
The "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; c…
What's the initial state supposed to be?
Infinite tape of zeros.
Re: BB(3, 4) > Ack(14)
#97Is it not true that BB(5) > BB(3,4)? On the 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.
Yes, 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.
I 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.
Re: BB(3, 4) > Ack(14)
#98Re: BB(3, 4) > Ack(14)
#99It 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…
> whereas in true spaghetti code each state would be able to pass to all the others.
An n-state s-symbol TM can transition to n other states at most (or halt). Thus, for s=4 or s=2, only the smallest of TMs could be spaghetti like.
Re: BB(3, 4) > Ack(14)
#100Can 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?
I found this quite helpful: 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.