modalduality

Most languages with monads have tools for working with them. In Haskell, for example, even without `liftM2` or `sequenceM`, you can simply do

    case (xm, ym) of
        (Just x, Just y) -> x + y
        _ -> 0

The main idea is to explore the concept of skinny triangles being unaesthetic (and thus undesirable for triangulations). This is true for many tasks in computational geometry, but not so true in art. Bringing these two together shows jarring conflict where the Delaunay Triangulation and your brain's sense of aesthetics disagree.

It's not really supposed to be useful, just exploration in reduction of an already reduced art style: what is lost when we enforce that all shapes are triangles that tend to be more large-angle? For one, I think this destroys the perspective since one common trope is to make objects narrower as they are farther away.

Although the entire thing is mostly a joke based on their shared last names.

Ah, so Aaronson is talking about the Busy beaver shifts function of 2 there. I gave the answer to the busy beaver function counting the maximum number of 1s.

> What makes it okay to identify the naming of a large number with producing that large number of things (e.g. 1's)?

Nice catch! I glossed over this but this is pretty important. The issue is that for any _specific number_, it takes a constant amount of time to write a number larger than that. Related: solving chess is technically O(1) since there are a constant number of positions we have to check.

What we need instead for this concept is a series of numbers, those can be compared with the question "Does one eventually get to a point where it will always be larger than the second?". We can parametrize the "biggest number" by the number of seconds given, say we can write down one character per second. Then a person's largest number function might be something like "f(n) = 9 ^ n", which is easy to see _is_ a computable function, and thus smaller than BB(n) for the same number of seconds, eventually.

In practice, just something like BB(100) - or BB(BB(100)), even can't really be written out by any computable method in a finite amount of time.

> which was: what characterizes the Busy Beaver function?

The proper one is just the number of 1s, but I talked about the shift function because it's easier to see why it's uncomputable. Tibor Rado proved that the Busy beaver function is also uncomputable in his 1962 paper, if you're interested you could check out his reduction.

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.