Hacker News new | past | comments | ask | show | jobs | submit login

We must know the percentage which halt! I can’t find it in the bbchallenge.org site, but every machine is categorized.



Not 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.




Consider applying for YC's Summer 2025 batch! Applications are open till May 13

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: