[HN Gopher] Cryptids
___________________________________________________________________
Cryptids
Author : frozenseven
Score : 123 points
Date : 2025-12-06 11:48 UTC (8 days ago)
(HTM) web link (wiki.bbchallenge.org)
(TXT) w3m dump (wiki.bbchallenge.org)
| jmclnx wrote:
| Very nice, not what I expected and worth a read!
| jbaber wrote:
| Your comment hinted I'd actually want to read it. Thanks!
| echelon wrote:
| > 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.
| tigereyeTO wrote:
| 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 **"
| 867-5309 wrote:
| 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
| grimgrin wrote:
| this is a cool link, not an ELI5, but
| https://nickdrozd.github.io/2020/10/04/turing-machine-
| notati...
| djmips wrote:
| Well I did learn about a new word "probviously" - very cool.
| JKCalhoun wrote:
| Scientific American, August 1984, "Computer Recreations" (p.
| 19) is where I first heard about busy beavers and Turing
| machines.
| motohagiography wrote:
| these remind me of rule 110 in GoL
| https://en.wikipedia.org/wiki/Rule_110
|
| are they related?
| Sharlin wrote:
| Weeell, sure, in the obvious sense that 110 is Turing complete.
| So you can encode any of these cryptids as a 110 initial
| pattern.
| dloranc wrote:
| 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.
| cryzinger wrote:
| 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
| Enginerrrd wrote:
| 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.
| cryzinger wrote:
| Ah that makes a lot of sense!
| baobun wrote:
| Once we have scalable quantum computers, fusion power, time
| travel and an indestructable material, I figure we can bundle
| all that together with instructions to send a particle back
| after T+1 on termination. Some problems will stay unsolved as
| they go on to the heat-death of the universe but maybe one or
| a few comes back with a useful result!
|
| Certainly with the right investments we'll get there within
| the next 5 years if you ask Musk and Altman. While a time
| machine might sound uncertain in that timefram, I'm sure AI
| will figure it out for us.
| jojomodding wrote:
| 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.
| lifis wrote:
| 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.
| kaidon wrote:
| Getting some Disco Elysium vibes here.
___________________________________________________________________
(page generated 2025-12-14 20:01 UTC)