BB(3, 4) > Ack(14)

Post by ziofill » Thu, May 23, 2024, 5:23 PM UTC

Post by kryptiskt » Thu, May 23, 2024, 5:25 PM UTC

wizzwizz4 wrote: post #20

Analemma_ wrote: post #11

Earlier quoted context omitted.

I 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.

But 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).

Post by nickdrozd » Thu, May 23, 2024, 5:28 PM UTC

LegionMammal978 wrote: post #35

nickdrozd wrote: post #29

It 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…

There 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. (Ever…

Post by sans-seraph » Thu, May 23, 2024, 5:39 PM UTC

nickdrozd wrote: post #30

supriyo-biswas wrote: post #4

Can 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…

    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 }
            }
        }
    }

Post by tromp » Thu, May 23, 2024, 5:47 PM UTC

ziofill wrote: post #41

There 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.