Show HN: Angelic-hierarchy, a game about Turing machines, philosophy, and math

In case you think you've figured out the 2-state solution and you want to check that you can't do better, I've uploaded the number of 1s your machine should output at https://modalduality.org/static/busy-beaver-2.txt, but did not include the actual configuration.

Thanks! I should probably include some more details on how to program the simulator.

Turing machines are just one simple way for formalizing programs, without all the complexities of modern programming languages. The core idea is that whatever a supercomputer (or any future computer) can compute, so can a Turing machine (it might just take more time): this is called the Church-Turing thesis.

The specifics on how to program Turing machines don't actually matter too much in modern complexity theory, but the rigorous basis is there when needed.

--

A Turing machine is always in some "state," (starts at A) and it's head is always over some cell of the tape, initially all zeros. Then the program, which is the grid in angelic hierarchy, specifies what the Turing machine should do. If it's in state A and the cell the head is at is 0, just go to the corresponding cell (marked in bright red), it will tell you the next state to go to, a number to write down on the tape, and a direction to step toward (Left or Right).

For intuition about why more states allow for more complex programs, try writing a 1-state program that writes two 1s and then halts (it's not possible). Then try it with 2 states.

Why can't we just go right and write 1s, staying in the same state for infinity ?

Hah, had the same thought myself.

Cool idea!

There were a couple points in the explanation which were kind of unclear to me, though:

What makes it okay to identify the naming of a large number with producing that large number of things (e.g. 1's)? This felt like a disconnect to me since in the introduction we are asked the largest number we can write down in 15 seconds, but my understanding is that the Busy Beaver functions aren't 'naming a number', but instead we're counting the number of 1's output by them (or maybe the function returns the number of ones rather than the string itself?). Actually, I think I'm starting to see the connection now: if we're considering the mathematical function rather than an executing program, then it just 'instantaneously' gives back a single number, and that single number is whatever sequence of ones the Turing machine would produce, which we could interpret as a reference to a numeric value rather than counting the digits? Maybe still a bit lost. Another way of stating my confusion: a person could easily write down a number larger than the number of 1's output by the 7-state solution (102*10^10^10^1870532) within 15 seconds (I could write that number down in maybe 5 seconds or so)—so in what sense is the Busy Beaver function naming a larger number?

There was another thing that tripped me up for a while, though I think I get it now, which was: what characterizes the Busy Beaver function? Is it that it "returns the maximum of the running times of all programs of length n that do eventually halt"—or is it that it "counts the number of 1's possible to be written by an n-state Turing machine before it halts"? It's pretty clear to me now that it's the latter, and that the former (the BBS function) is just one implementation of the general concept, but it gave me some trouble to figure that out.