3 ms·
Even if it is halting, you can sometimes statically detect if a Turing machine never halts. Just look through the state machine and see if any states will trans
by roywiggins 4y ago
Even if it is halting, you can sometimes statically detect if a Turing machine never halts. Just look through the state machine and see if any states will transition to a halt; if none of them do, the machine will loop forever. This is not a very large fraction of machines that loop forever, but if you're writing a machine and want to be absolutely sure it won't halt, just don't put in any states that halt.