Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

BB(3, 4) > Ack(14)

sligocki.com

Post reply on HN
Print view View original

101–110 of 114 posts

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

#101

Post by wwalexander »

dataflow wrote: post #95
nickdrozd wrote: post #30

Earlier 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?

My understanding is that the states are conventionally listed in order, so A would be the initial state:

> A TM string is in lexical normal form iff the following conditions obtain: …The non-initial active states first occur in ascending order…

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

#103

Post by LegionMammal978 »

AlotOfReading wrote: post #55
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…

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

Of course, there can't be some grand global structure to describe all the champions in one go. But there could be properties that many have in common, e.g., predominantly consisting some number of nested recursions, characterized by some transfinite ordinal. For instance, this particular machine recurses over the first several hyperoperations.

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

#104

Post by LegionMammal978 »

__MatrixMan__ wrote: post #90
kingofthecob wrote: post #52

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

The acronyms refer to: https://en.wikipedia.org/wiki/Busy_beaver 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…

Well, 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

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

#105

Post by Aardwolf »

tromp wrote: post #10

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

Hmm, so I think the 1R in 1RZ don't matter then for this program and are arbitrarily chosen, since it halts there so it doesn't matter what's still written on the tape or where the tape head moves?

(Even writing of the 1 doesn't matter, though a 0 would have been suboptimal I guess. A 2 was already written on the tape there, it's being replaced by a 1 but the 2 counted just as much for 'number of symbols on the tape')

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

#106

Post by [deleted] »

casercaramel144 wrote: post #72

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

[deleted]

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

#108

Post by koromak »

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

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

#109

Post by earthboundkid »

koromak wrote: post #108

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

https://www.scottaaronson.com/writings/bignumbers.html

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

#110

Post by addaon »

jonahx wrote: post #92
sligocki wrote: post #74

Earlier quoted context omitted.

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.

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

If the Halting problem could be solved by intuition, it wouldn't be much of a problem.

Post reply on HN