I think that refers to turing machines that never halt at standard numbers of steps (i.e. it would halt at infinity, or more formally ω, which is a nonstandard number). It might also represent halting at a negative time (i.e. if you ran the turing machine backwards for N steps, then forward again for less than N steps, it would halt, but otherwise doesn’t halt). Anything that fails to halt in a standard number of steps can be considered to halt in a nonstandard number of steps, if you include the restraint that there has to be a value X such that it halts in X steps. By that definition, a turing machine halts if and only if X is a standard number. I could be wrong though.
Eliezer isn’t asking about how long a particular Turing machine takes to halt—he’s asking the binary question, “Will it halt or not?” As far as I could tell, Eliezer was claiming that there exist Turing machines that don’t halt, but that we can’t prove don’t halt using first-order Peano arithmetic. The particular example was to show how this claim was plausible (and, in fact, true).
If you ran the Turing machine backwards for N steps...
In some cases, this isn’t even a well-defined operation.
Anything that fails to halt in a standard number of steps...
Fails to halt. The standard numbers are the ones we care about. It’s the proof that this is the case that is nontrivial, and in some cases requires second-order logic (or at least, that’s what I think Eliezer is claiming). But you don’t always need second-order logic, so what you said (”...can be considered to halt in a nonstandard number of steps”, and really, this should be, “on a step corresponding to a nonstandard number”) was wrong.
By the way, ω isn’t a nonstandard number in countable nonstandard models of Peano arithmetic. It’s an ordinal number, not a cardinal number, so I’m not even exactly sure what you mean...but a Turing machine can’t halt at time infinity, because there’s no such thing as “time infinity”.
It should refer to a Turing machine that never halts but cannot be proven in Peano arithmetic not to halt. The second condition is important (otherwise it would just be a Turing machine that never halts, period). I know how to write down such a Turing machine (edit: for an explicit example, consider a Turing machine which is searching for a contradiction in PA); what I don’t know is how this definition can be related to a definition in terms of defining what it means to run a Turing machine for a nonstandard number of steps.
It doesn’t necessarily make sense to talk about running a Turing machine backwards. Also, models of first-order Peano arithmetic do not contain negative numbers; this is ruled out by the axiom that 0 is not a successor.
I don’t think it could halt at a negative time. If it did, it would have to stay halted, which would mean that it would still be halted at zero, so the program halts in the natural numbers.
I think that refers to turing machines that never halt at standard numbers of steps (i.e. it would halt at infinity, or more formally ω, which is a nonstandard number). It might also represent halting at a negative time (i.e. if you ran the turing machine backwards for N steps, then forward again for less than N steps, it would halt, but otherwise doesn’t halt). Anything that fails to halt in a standard number of steps can be considered to halt in a nonstandard number of steps, if you include the restraint that there has to be a value X such that it halts in X steps. By that definition, a turing machine halts if and only if X is a standard number. I could be wrong though.
Eliezer isn’t asking about how long a particular Turing machine takes to halt—he’s asking the binary question, “Will it halt or not?” As far as I could tell, Eliezer was claiming that there exist Turing machines that don’t halt, but that we can’t prove don’t halt using first-order Peano arithmetic. The particular example was to show how this claim was plausible (and, in fact, true).
In some cases, this isn’t even a well-defined operation.
Fails to halt. The standard numbers are the ones we care about. It’s the proof that this is the case that is nontrivial, and in some cases requires second-order logic (or at least, that’s what I think Eliezer is claiming). But you don’t always need second-order logic, so what you said (”...can be considered to halt in a nonstandard number of steps”, and really, this should be, “on a step corresponding to a nonstandard number”) was wrong.
By the way, ω isn’t a nonstandard number in countable nonstandard models of Peano arithmetic. It’s an ordinal number, not a cardinal number, so I’m not even exactly sure what you mean...but a Turing machine can’t halt at time infinity, because there’s no such thing as “time infinity”.
I really, honestly, don’t mean this reply to come off as condescending. I think it would help you to read through the Wikipedia article on Turing machines.
It should refer to a Turing machine that never halts but cannot be proven in Peano arithmetic not to halt. The second condition is important (otherwise it would just be a Turing machine that never halts, period). I know how to write down such a Turing machine (edit: for an explicit example, consider a Turing machine which is searching for a contradiction in PA); what I don’t know is how this definition can be related to a definition in terms of defining what it means to run a Turing machine for a nonstandard number of steps.
It doesn’t necessarily make sense to talk about running a Turing machine backwards. Also, models of first-order Peano arithmetic do not contain negative numbers; this is ruled out by the axiom that 0 is not a successor.
I don’t think it could halt at a negative time. If it did, it would have to stay halted, which would mean that it would still be halted at zero, so the program halts in the natural numbers.