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: Benja 20 December 2012 04:58:53PM 7 points [-]

Yeah, there's a little non-obvious trick to talking about properties of Turing machines in the language of arithmetic, which is essential to understanding this.

The first thing you do is to use a little number theory to define a bijection between natural numbers and finite lists of natural numbers. Next, you define a way to encode the status of a Turing machine at one point in time as a list of numbers (giving the current state and the contents of the tapes); with your bijection, you can encode the status at one point in time as a single number. Now, you encode execution histories as finite lists of status numbers, which your bijection maps to a single number. You can write "n denotes a valid execution history that ends in a halting state" (i.e., n is a list of valid statuses, with the first one being a start status, the last one being a halting status, and each intermediate one being the uniquely determined correct successor to the previous one). After doing all this work, you can write a formula in the language of arithmetic saying "the Turing machine m halts on input i", by simply saying "there is an n which denotes a valid execution history of machine m, starting at input i and ending in a halting state".

Now consider an execution history consisting of a "finite" list of nonstandard length.

Comment author: Qiaochu_Yuan 20 December 2012 07:44:29PM *  2 points [-]

Okay, this is what I suspected after thinking about it for a bit, but like earthwormchuck it is not clear to me in what sense we are "really" talking about running Turing machines for a nonstandard number of steps here... the interpretation I had in mind in the case of an ultrapower of the standard model is more direct: namely, running a Turing machine for the nonstandard number of steps (a1, a2, a3, ...) ought to mean considering the sequence of states of the Turing machine after steps a1, a2, a3, ... as an element of the ultrapower of the set of possible states of the Turing machine (in other words, after nonstandard times, the Turing machine may be in nonstandard states). It is not clear to me whether we have such an interpretation in general.

Comment author: Benja 20 December 2012 08:10:15PM 11 points [-]

Ok -- as I replied to earthwormchuck, I think Eliezer isn't saying at all that there is a useful way in which these nonstandard execution histories are "really" talking about Turing machines, he's saying the exact opposite: they aren't talking about Turing machines, which is bad if you want to talk about Turing machines, since it means that first-order logic doesn't suffice for expressing exactly what it is you do want to talk about.

Comment author: Sniffnoy 20 December 2012 08:55:43PM 6 points [-]

WIth that interpretation, you couldn't have a halt at a nonstandard time without halting at some standard time, right? If it were halted at some nonstandard time, it would be halted at almost all the standard times in that nonstandard time (here "almost all" is with respect to the chosen ultrafilter), and hence in particular at some standard time.

(Add here standard note for readers unused to infinity that it can be made perfectly sensible to talk about Turing machines running infinitely long and beyond but this has nothing to do with what's being talked about here.)

Comment author: Qiaochu_Yuan 20 December 2012 09:26:42PM 1 point [-]

Ah. Right. Somehow I totally forgot about Łoś's theorem.