3 ms·
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 equivalen
by cyberax 3y ago
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.
- EscapeFromNY 3y agoThanks, that's a perfect explanation