anonymous1 comments on Standard and Nonstandard Numbers - Less Wrong

31 Post author: Eliezer_Yudkowsky 20 December 2012 03:23AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (83)

You are viewing a single comment's thread. Show more comments above.

Comment author: [deleted] 20 December 2012 04:33:43PM 3 points [-]

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".

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.