Hacker Newsnew | past | comments | ask | show | jobs | submitlogin
Seemingly Impossible Turing Machines (playingwithpointers.com)
2 points by sanjoy_das on July 14, 2019 | hide | past | favorite | 1 comment


My intuition tells me that no Turing machine that terminates for all unbounded inputs can run "much longer than" a busy-beaver turing machine. However, the numbers that describe how long BBs can run are .. quite large. The numbers might as well be infinite in any practical sense.




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

Search: