If we can't predict/model these Turing machines' behavior because of unsolved math problems, what's stopping us from actually creating and running them to see what would happen (and maybe getting closer to solving those math problems in the process)? Is it just a matter of scale and resources?
My knowledge here is very limited, so this isn't a "why has no one tried this one weird trick"-type question. I assume there is in fact a good reason that I don't yet understand :P
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.
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.
> 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.
If we can't predict/model these Turing machines' behavior because of unsolved math problems, what's stopping us from actually creating and running them to see what would happen (and maybe getting closer to solving those math problems in the process)? Is it just a matter of scale and resources?
My knowledge here is very limited, so this isn't a "why has no one tried this one weird trick"-type question. I assume there is in fact a good reason that I don't yet understand :P
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.
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.
Ah that makes a lot of sense!
I had no idea what this was talking about and followed links to a blog post that explained the first one ("Bigfoot"): https://www.sligocki.com/2023/10/16/bb-3-3-is-hard.html
This blog post made the "cryptids" make a lot more sense to me, so I thought I'd share that post here in case others were also wondering "what the **"
Well I did learn about a new word "probviously" - very cool.
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
this is a cool link, not an ELI5, but https://nickdrozd.github.io/2020/10/04/turing-machine-notati...
Very nice, not what I expected and worth a read!
> 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!
these remind me of rule 110 in GoL https://en.wikipedia.org/wiki/Rule_110
are they related?