= 27d567bc2d48d9f40e9ccc20ea370b15)
Qiaochu_Yuan comments on Standard and Nonstandard Numbers - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (83)
Can you (or someone else too, I guess) give an example of a Turing machine with a nonstandard halting time? It's not clear to me what you mean by running a Turing machine for a nonstandard number of steps. (I think I can make this meaningful in my favorite nonstandard model of Peano arithmetic, namely an ultrapower of the standard model, but I don't see how to make it meaningful in general.)
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.
You get a formula which is true of the standard numbers m and i if and only if the m'th Turing machine halts on input i. Is there really any meaningful sense in which this formula is still talking about Turing machines when you substitute elements of some non-standard model?
In a sense, no. Eliezer's point is this: Given the actual Turing machine with number m = 4 = SSSS0 and input i = 2 = SS0, you can substitute these in to get a closed formula φ whose meaning is "the Turing machine SSSS0 halts on input SS0". The actual formula is something like, "There is a number e such that e denotes a valid execution history for machine SSSS0 on input SS0 that ends in a halting state." In the standard model, talking about the standard numbers, this formula is true iff the machine actually halts on that input. But in first-order logic, you cannot pinpoint the standard model, and so it can happen that formula φ is false in the standard model, but true in some nonstandard model. If you use second-order logic (and believe its standard semantics, not its Henkin semantics), formula φ is valid, i.e. true in every model, if and only if machine 4 really halts on input 2.
Okay. This is exactly what I thought it should be, but the way Eliezer phrased things made me wonder if I was missing something. Thanks for clarifying.
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.
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.
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.)
Ah. Right. Somehow I totally forgot about Łoś's theorem.
Disclaimer: I am not familiar with the formalities of Turing machines, and am quite possibly talking out of my ass, and probably not thinking along the same lines as Eliezer here. But it might be possible to salvage the ideas into something more formal/correct.
Consider a model containing exactly the natural numbers and the starred chain. Then we might have a Turing machine which starts at 0 and 0* , halts if it is fed 0*, and continues to the successor otherwise. Then it never halts on the natural chain, but halts immediately on the starred chain. Here, a Turing machine presumably operates on every chain in a model meeting the first-order Peano axioms.
So in general, it might be meaningful to talk of a Turing machine acting within a model containing chains, which is closed on every given chain (e.g. it can't jump from 0 to 0* ), and which could therefore be said to be associated by a 'halt time' function, h, which maps each chain (or each chain's zero, if you like) to a nonnegative number in that chain which is the halting time on that chain. So in my above example, we might leave h(0) undefined, because the machine never halts on the naturals, and h(0* )=0*, because it halts immediately on that chain. This would then completely define the halting time over chains. (In fact, we could probably drop closure if we wanted to.)
(Edited:) I think you're conflating the natural numbers and the tape that the Turing machine runs on. Interpreting "nonstandard halting time," the way I think Eliezer is using the term, doesn't require changing our notion of what a tape is; it just requires translating the statement "this Turing machine is in state s at time t" into a statement in Peano arithmetic (where t is a natural number) and then interpreting it in a nonstandard model.