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

Think about it like this, there are infinitely many Turing machine state classes that are easily decidable. For example, a simple infinite loop or its equivalent. Most of these classes are also very trivial to construct, and require only a few "instructions".

So if you make a random TM, it's almost guaranteed that it'll get eventually "trapped" in one of these easily decidable infinite loops.



Thanks, that's a perfect explanation




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

Search: