2 ms·
Yes, it has the halting problem for a machine much less powerful than a Turing machine, where the answer is always yes unless the thermostat fails. The idea is
by whatshisface 9y ago
Yes, it has the halting problem for a machine much less powerful than a Turing machine, where the answer is always yes unless the thermostat fails. The idea is that just like there are programs less powerful than the halting oracle there are statements less powerful than the completeness of arithmetic.