←back to thread

Turing-Drawings

(github.com)
142 points laurenth | 1 comments | | HN request time: 0.377s | source
1. Xcelerate ◴[] No.43750816[source]
If I had to guess, I would say that of the ones with more than a few states and symbols that do not halt (i.e. reach a static image configuration), modern mathematics (ZFC) probably cannot prove that fact for most of them. The Busy Beaver project managed it for all 5 state, 2 symbol machines on the empty tape, but IIRC they’re uncertain whether BB(6) is ZFC-provable. (Someone from that project correct me if I’m wrong.)

I find that fascinating. Small scale computation (exploring Turing machine behavior, cellular automata, etc.) is mostly considered a curiosity within the hobbyist realm at the moment, but I suspect that will change over time as we develop better and better tools to characterize computation.