Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I mean, any given Turing machine has finite code. But with even a very small number of states you start getting into crazy territory.

We’ve constructed Turing machines with fewer than 800 states that halt if and only if ZFC is inconsistent. Which means that even given infinite time and space, we still couldn’t find BB(800) without fundamentally changing our system of mathematics.



Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

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

Search: