It’s possible to compute whether each machine halts using an inductive Turing machine like this:
initialize output tape to all zeros, representing the assertion that no Turing machine halts
for i = 1 to infinity
. for j = 1 to i
. . run Turing machine j for i steps
. . if it halts: set bit j in the output tape to 1
Is this what you meant? If so, I’m not sure what this has to do with observing loops.
When you say that every nonhalting Turing machine has some kind of loop, do you mean the kind of loop that many halting Turing machines also contain?
When you say that every nonhalting Turing machine has some kind of loop, do you mean the kind of loop that many halting Turing machines also contain?
No, I mean precisely the fact that it doesn’t halt. You can think of it as an infinitely growing recursion if that helps, but what’s in question is really precisely the nonhalting behavior.
I’m going to make a Discussion post about the matter, since Luke wants me to share the whole informal shpiel on the subject.
It’s possible to compute whether each machine halts using an inductive Turing machine like this:
Is this what you meant? If so, I’m not sure what this has to do with observing loops.
When you say that every nonhalting Turing machine has some kind of loop, do you mean the kind of loop that many halting Turing machines also contain?
No, I mean precisely the fact that it doesn’t halt. You can think of it as an infinitely growing recursion if that helps, but what’s in question is really precisely the nonhalting behavior.
I’m going to make a Discussion post about the matter, since Luke wants me to share the whole informal shpiel on the subject.