Qiaochu_Yuan 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: Qiaochu_Yuan 20 December 2012 07:01:55AM *  3 points [-]

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.