Cryptids

> Cryptids are Turing Machines whose behavior (when started on a blank tape) can be described completely by a relatively simple mathematical rule, but where that rule falls into a class of unsolved (and presumed hard) mathematical problems. This definition is somewhat subjective (What counts as a simple rule? What counts as a hard problem?). In practice, most currently known small Cryptids have Collatz-like behavior. In other words, the halting problem from blank tape of Cryptids is mathematically-hard.

Your comment hinted I'd actually want to read it. Thanks!

came to comments after tfa didn't explain anything, saw your comment and thought whew, clicked the link and now I'm even more confused

Well I did learn about a new word "probviously" - very cool.

Scientific American, August 1984, "Computer Recreations" (p. 19) is where I first heard about busy beavers and Turing machines.

You can encode any Turing machine as initial state for rule 110, but as far as I know it isn't useful for studying Busy Beavers.

Weeell, sure, in the obvious sense that 110 is Turing complete. So you can encode any of these cryptids as a 110 initial pattern.

I’m a little out of my depth, but I’d guess a lot of them would probably fall into one of two categories: Something we believe should go on forever (and not halt) if the math problem is resolved the way we expect, but theoretically could suddenly halt after some absurdly long number of steps. Or something where it halts for a given input after some number of steps unless something some counter example exists where it goes on forever.

In the first, you can’t really do anything but just keep watching it not halt but it isn’t telling you anything about the infinity to go. (Say a program that spits out twin primes, we expect an infinite number but we don’t really know)

And in the second case we’d just have to keep trying larger and larger inputs making this just an extension of the first category if we wrote a program to do that for us. And if we did find an example where it goes on forever without repeating states, how would you even know? It’d be like the first situation again.

Consider, for example, the "Hydra" cryptid (second in the list OOP linked).

This is a BB(2,5) machine (2 states, 5 symbols). There are other BB(2,5) machines that take more than 10↑↑4 steps to terminate. And the "Hydra" is called a cryptid because it might run even longer than that. So "naively" running it is unlikely to yield results before the heat death of the universe.

Of course, you can run it more cleverly by looking at what the machine is doing and essentially re-implementing this in a faster language. People have in fact done this, and simulated 4 million "fast" steps (corresponding to much more "naive" steps), and not found it to halt. If you want to run the simulation yourself, the code is on the website OOP linked, in the article about the Hydra.

In some cases, yes, it’s just a matter of scale and resources. But to an extreme degree, such as requiring far more compute than will ever exist in this universe.

In other cases, no amount of compute would be enough because the unresolved question is whether or not program ever terminates. The compute available in the physical universe is probably finite. No finite amount of compute is sufficient to prove that a program never terminates, because it doesn’t rule out the possibility that it might terminate if you ran it just a little longer.

That is what motivates using mathematical analysis to try to figure out how these systems behave over time in a more efficient way than simulating them step by step.

If a Turing machine halts, then we can always prove that fact using a formal theory at least as powerful as Robinson arithmetic (so Peano Arithmetic, aka “grade school math”, is sufficient). The program’s execution trace is essentially the proof that it halts.

However, in the case where a Turing machine does not halt, we can only sometimes prove that fact, and whether we can depends on the strength of the theory we use. You wonder whether there is a theory with a finite description that is strong enough to prove all non-halting machines never halt, but this isn’t possible. Why? Because for any such theory, you can write a program that iterates over all infinite proofs of the theory (via breadth first search) looking for a contradiction (e.g. a proof that 0=1), and halts if one is discovered. Gödel’s second incompleteness theorem entails that if the theory actually is consistent (and sufficiently powerful), then it cannot prove this own program involving itself will ever halt.

So that’s why running the program and seeing what happens doesn’t necessarily help in this case—you can always construct new problems (does this machine halt?) that are unprovable within any consistent and sound, finitely axiomatizable theory.

That only provides a proof if the machine halts in a number of steps that you can compute. Otherwise, it is unable to determine whether the machine halts later or doesn't halt at all, which is the current situation.