BB(3, 4) > Ack(14) • Hacker News Board

Re: BB(3, 4) > Ack(14)

#51

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

nickdrozd wrote: post #45

LegionMammal978 wrote: post #35

Earlier quoted context omitted.

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…

> streetlamp effect I agree completely, all of these kinds of conjectures are shaped by what is detectable. If there are any "dark matter" programs out there, they by definition will be difficult to find. That said, I find it entirely plausible that the champions will win by exploiting complex and exotic mathematical facts, while the implementations of the math do not themselves need to be complex or exotic at the co…

Yeah, thankfully we're still in the range where halting machines are at least estimable in terms of inductive notations like the up-arrow. But as the machines gain more breathing room for working with variable-length data, we can start getting monsters like the TREE sequence.

Re: BB(3, 4) > Ack(14)

#52

Post by kingofthecob » Thu, May 23, 2024, 6:00 PM UTC

If you know, you know I guess. I certainly have no idea.

Re: BB(3, 4) > Ack(14)

#53

Post by lisper » Thu, May 23, 2024, 6:01 PM UTC

JadeNB wrote: post #39

lisper wrote: post #28

Earlier quoted context omitted.

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 haven't. I suspect that these are extremely rare and valuable collectors items and only trained archivists are even allowed to handle them. I'm not sure that they're collector's items, but they're probably not in that many university libraries. For example, the University of Michigan library has a physical copy in its special…

What difference does it make if the original lasts a year or a century? The original is irrelevant except for historical purposes. What matters from a scientific point of view is that the results withstand scrutiny, and that they are reliably replicated and accessible.

Re: BB(3, 4) > Ack(14)

#54

Post by lisper » Thu, May 23, 2024, 6:02 PM UTC

vlovich123 wrote: post #38

lisper wrote: post #37

Earlier quoted context omitted.

> Financial pressures to publish or perish But those only exist because of the current peer-review model. There is a huge non-linearity built in to the publication process that provides disproportionate rewards for conning a small number of people, fewer than half a dozen. That, combined with a presumption of trustworthiness, produces a perverse incentive for attempting such cons because they are very easy to pull of…

The rewards come from the grant model which I forgot to mention and also has similar problems to peer review. The stipulation to publish is a secondary effect. If peer review didn’t exist there would still be pressure to show that you somehow convinced the leading experts in the field.

> there would still be pressure to show that you somehow convinced the leading experts in the field

And how do you tell who are the leading experts in the field?

Re: BB(3, 4) > Ack(14)

#55

Post by AlotOfReading » Thu, May 23, 2024, 6:10 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…

Handwaving here, but I think longest running machines can't follow a specific structure in general.

Rough sketch of an argument:

Let's construct a number from all intermediate states of the machine concatenated. The number of digits of this number should correspond to the runtime (sketchy). We only care about the halting machines, so it's finite. We know that it must be unique because if a smaller machine computes the same number, we could get a bigger number by simply running the smaller program and doing other nonsense. That means the biggest programs are komolgorov optimal, and the numbers themselves should be k-trivial and thus nearly but not quite computable. Since they're not computable, the programs themselves can't follow a structure to generate them (since that would be computable in turn for larger values).

Re: BB(3, 4) > Ack(14)

#56

Post by vlovich123 » Thu, May 23, 2024, 6:12 PM UTC

lisper wrote: post #54

vlovich123 wrote: post #38

Earlier quoted context omitted.

The rewards come from the grant model which I forgot to mention and also has similar problems to peer review. The stipulation to publish is a secondary effect. If peer review didn’t exist there would still be pressure to show that you somehow convinced the leading experts in the field.

> there would still be pressure to show that you somehow convinced the leading experts in the field And how do you tell who are the leading experts in the field?

It doesn’t matter. There’s plenty of ways. Tenure, those who get cited the most as contributing to other works, whoever manages to shmooze their way onto the grant review board, whoever has been doing “good” work in a space etc etc. If you think that peer review is the only way status is established, I’m afraid you’re failing to grok how humans work - we’re very status oriented and will come up with any mechanism to formalize and broadcast that status and academia and the scientific world is not immune from this.

Re: BB(3, 4) > Ack(14)

#57

Post by nilstycho » Thu, May 23, 2024, 6:14 PM UTC

im3w1l wrote: post #50

tromp wrote: post #46

Earlier quoted context omitted.

I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.

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

Also, 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?

Re: BB(3, 4) > Ack(14)

#58

Post by tromp » Thu, May 23, 2024, 6:16 PM UTC

im3w1l wrote: post #50

tromp wrote: post #46

Earlier quoted context omitted.

I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.

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

Only if you want to count the number of different possible TM behaviours. The official count of BB TMs as given in OEIS sequence A052200 ignores such symmetries.

[1] https://oeis.org/A052200

Re: BB(3, 4) > Ack(14)

#59

Post by AlotOfReading » Thu, May 23, 2024, 6:18 PM UTC

lisper wrote: post #53

JadeNB wrote: post #39

Earlier quoted context omitted.

> 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. I'm not sure that they're collector's items, but they're probably not in that many university libraries. For example, the University of Michigan library has a physical copy in its special…

What difference does it make if the original lasts a year or a century? The original is irrelevant except for historical purposes. What matters from a scientific point of view is that the results withstand scrutiny, and that they are reliably replicated and accessible.

We discover new approaches to replication all the time. Have you never come across foundational papers and arguments that everyone loved at the time, but made big methodological mistakes that led to the wrong conclusion? Or worse, found a source everyone references based on yet other secondary sources, only to look at the original context to discover that everyone's been misquoting it for decades? That happens regularly.

Re: BB(3, 4) > Ack(14)

#60

Post by jamesaross » Thu, May 23, 2024, 6:18 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…

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 ; goto *B[SCAN];
    A2: WRITE(1); RIGHT; HALT; return 0;
    A3: WRITE(2); RIGHT; goto *A[SCAN];
    B0: WRITE(2); LEFT ; goto *C[SCAN];
    B1: WRITE(3); RIGHT; goto *B[SCAN];
    B2: WRITE(1); LEFT ; goto *C[SCAN];
    B3: WRITE(2); RIGHT; goto *A[SCAN];
    C0: WRITE(3); RIGHT; goto *B[SCAN];
    C1: WRITE(1); LEFT ; goto *B[SCAN];
    C2: WRITE(3); LEFT ; goto *C[SCAN];
    C3: WRITE(2); RIGHT; goto *C[SCAN];
  }