4 ms·
Can We Decide Whether Small Computer Programs Halt?
- VLM 13y agoI thought it weird that the guy who proposed n=7 wouldn't explain why, it probably boils down to something like you can implement 1-D cellular automaton rule 110 with n=8 (or smaller?) so he was probably aiming at something like "halt if you get more than a certain 1's density in a certain range" or something equally unprovable other than by running the thing. Or he has a way to make a Turing machine emulator in n=7.