2 ms·
According to Scott Aaronson's blog post on this, there are 16,679,880,978,201 5-state Turing machines. I wonder if we know what percentage of them halt? Edit:
by ks2048 2y ago
According to Scott Aaronson's blog post on this, there are 16,679,880,978,201 5-state Turing machines. I wonder if we know what percentage of them halt?
Edit: number of TM for n states: (4n + 1)^(2n). Found this (for smaller n), which is the kind of analysis I was curious about: https://github.com/LukasKalbertodt/beaver https://github.com/LukasKalbertodt/beaver
- srcreigh 2y agoWe must know the percentage which halt! I can’t find it in the bbchallenge.org site, but every machine is categorized.
- LegionMammal978 2y agoNot necessarily. The seed database only contains TMs in tree normal form (TNF), which already contains several reductions. To convert the percentage of TNF halters to the percentage of total halters, you'd have to account for the multiplicity of each TNF machine, which is a bunch of fiddly combinatorics. Also, you'd have to add the machines that have no TNF form due to never writing a 1 to the tape.