3 ms·
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 t
by jojomodding 10mo ago
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.
- csense 10mo ago10↑↑4 is Knuth's arrow notation, it means 10^(10^(10^10)). Which is really big. The inner exponent 10^10000000 is already way, way over the limit of computational steps you have any hope of physically computing [2] without some kind of algorithmic shortcut. [1] https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation https://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation [2] I wave my hands and put this limit at about 10^70. The universe has ~10^40 atoms and a trillion years is ~10^30 nanoseconds. So 10^70 is approximately "How many computations you could do if you turned every atom in the universe into a 1 GHz CPU and ran them for a trillion years." (Assuming magical technology that doesn't need power / cooling / communications and parallelizes perfectly.)