Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

 2 added 294 characters in body edited Jun 11 '14 at 16:21 commando 6,08566 gold badges3232 silver badges6666 bronze badges I think you've essentially rediscovered the undecidability of the Halting Problem. This is the statement that it is impossible to write a program that can determine whether any program will terminate. The actual proof uses some rather involved logic, but the result can be summarized by the following counterexample: write a program that takes the output of a hypothetical Halting program when run on itself, and terminate if and only if the Halting program predicted that the program would not terminate. This contradicts the Halting program, therefore such a universal program cannot exist. Within the context of a model for the universe, my hypothetical explanation deals with how such a model would have to work. Suppose that we know a deterministic model for the universe, and from this construct a function called `Predict10`. This function takes any complete `state` as input and returns `newState`, which is what `state` is predicted to evolve to in ten seconds. `Predict10(state) = newState` Note that each state consists of many many points spread out across whichever (closed) system you're running the model on. `Predict10` will function by applying the rules of the model to each point in `state`, taking into account every other relevant point. Essentially each point in `newState` is determined by a (presumably very complicated) series of equations operating on `state`. Let the current state of this very universe be `thisState`, and let `nextState = Predict10(thisState)`. Suppose we look at the Andromeda galaxy in `nextState`. The state of every point in the Andromeda galaxy will be determined by the aforementioned equations derived from our model. Of particular note is that, since the Andromeda galaxy ten seconds into the future is not in our (the observers') light cone, the fact that we use `Predict10` at `thisState` can have no bearing on `nextState` in Andromeda. That is, our use of `Predict10` is not part of the equations used to determine Andromeda in `nextState`. Thus we cannot "interfere" with the deterministic model's results for Andromeda, and the equations should converge to some reasonable answer yielding Andromeda ten seconds in the future. Now, instead suppose that we want to look at the state of my computer in `nextState`. Here is where we run into a problem. Take any point in my computer, and consider the equations that go into determining its `nextState`. Part of these equations will be the fact that I use `Predict10`, since the point is in that event's light cone. However, the point is also in the light cone of my response to the result of `Predict10` - and there's the rub. We need to know how I will respond to `Predict10` in order to finish computing `Predict10` for any point in my light cone (beyond points that take place before I've had sufficient neurological time to respond), but we cannot know how I will respond unless we finish the computation. It's a sort of catch-22 that prevents our algorithm from working in this situation. There's nothing inherently wrong with our model; it just can't converge to a solution in certain regions of the universe because of the above problem. So in summary, your thought experiment doesn't disprove the possibility of a deterministic model per se. Rather it demonstrates (roughly) that any such deterministic model will have limitations in its range of application, though there should still be places where it functions perfectly. As a final disclaimer, note that all this is heavily related to much more concretized problems in the study of differential equations. That is the field of mathematics (and physics) which deals with precisely the question of how states evolve over time. I think you've essentially rediscovered the undecidability of the Halting Problem. This is the statement that it is impossible to write a program that can determine whether any program will terminate. The actual proof uses some rather involved logic, but the result can be summarized by the following counterexample: write a program that takes the output of a hypothetical Halting program when run on itself, and terminate if and only if the Halting program predicted that the program would not terminate. This contradicts the Halting program, therefore such a universal program cannot exist. Within the context of a model for the universe, my hypothetical explanation deals with how such a model would have to work. Suppose that we know a deterministic model for the universe, and from this construct a function called `Predict10`. This function takes any complete `state` as input and returns `newState`, which is what `state` is predicted to evolve to in ten seconds. `Predict10(state) = newState` Note that each state consists of many many points spread out across whichever (closed) system you're running the model on. `Predict10` will function by applying the rules of the model to each point in `state`, taking into account every other relevant point. Essentially each point in `newState` is determined by a (presumably very complicated) series of equations operating on `state`. Let the current state of this very universe be `thisState`, and let `nextState = Predict10(thisState)`. Suppose we look at the Andromeda galaxy in `nextState`. The state of every point in the Andromeda galaxy will be determined by the aforementioned equations derived from our model. Of particular note is that, since the Andromeda galaxy ten seconds into the future is not in our (the observers') light cone, the fact that we use `Predict10` at `thisState` can have no bearing on `nextState` in Andromeda. That is, our use of `Predict10` is not part of the equations used to determine Andromeda in `nextState`. Thus we cannot "interfere" with the deterministic model's results for Andromeda, and the equations should converge to some reasonable answer yielding Andromeda ten seconds in the future. Now, instead suppose that we want to look at the state of my computer in `nextState`. Here is where we run into a problem. Take any point in my computer, and consider the equations that go into determining its `nextState`. Part of these equations will be the fact that I use `Predict10`, since the point is in that event's light cone. However, the point is also in the light cone of my response to the result of `Predict10` - and there's the rub. We need to know how I will respond to `Predict10` in order to finish computing `Predict10` for any point in my light cone (beyond points that take place before I've had sufficient neurological time to respond), but we cannot know how I will respond unless we finish the computation. It's a sort of catch-22 that prevents our algorithm from working in this situation. There's nothing inherently wrong with our model; it just can't converge to a solution in certain regions of the universe because of the above problem. As a final disclaimer, note that all this is heavily related to much more concretized problems in the study of differential equations. That is the field of mathematics (and physics) which deals with precisely the question of how states evolve over time. I think you've essentially rediscovered the undecidability of the Halting Problem. This is the statement that it is impossible to write a program that can determine whether any program will terminate. The actual proof uses some rather involved logic, but the result can be summarized by the following counterexample: write a program that takes the output of a hypothetical Halting program when run on itself, and terminate if and only if the Halting program predicted that the program would not terminate. This contradicts the Halting program, therefore such a universal program cannot exist. Within the context of a model for the universe, my hypothetical explanation deals with how such a model would have to work. Suppose that we know a deterministic model for the universe, and from this construct a function called `Predict10`. This function takes any complete `state` as input and returns `newState`, which is what `state` is predicted to evolve to in ten seconds. `Predict10(state) = newState` Note that each state consists of many many points spread out across whichever (closed) system you're running the model on. `Predict10` will function by applying the rules of the model to each point in `state`, taking into account every other relevant point. Essentially each point in `newState` is determined by a (presumably very complicated) series of equations operating on `state`. Let the current state of this very universe be `thisState`, and let `nextState = Predict10(thisState)`. Suppose we look at the Andromeda galaxy in `nextState`. The state of every point in the Andromeda galaxy will be determined by the aforementioned equations derived from our model. Of particular note is that, since the Andromeda galaxy ten seconds into the future is not in our (the observers') light cone, the fact that we use `Predict10` at `thisState` can have no bearing on `nextState` in Andromeda. That is, our use of `Predict10` is not part of the equations used to determine Andromeda in `nextState`. Thus we cannot "interfere" with the deterministic model's results for Andromeda, and the equations should converge to some reasonable answer yielding Andromeda ten seconds in the future. Now, instead suppose that we want to look at the state of my computer in `nextState`. Here is where we run into a problem. Take any point in my computer, and consider the equations that go into determining its `nextState`. Part of these equations will be the fact that I use `Predict10`, since the point is in that event's light cone. However, the point is also in the light cone of my response to the result of `Predict10` - and there's the rub. We need to know how I will respond to `Predict10` in order to finish computing `Predict10` for any point in my light cone (beyond points that take place before I've had sufficient neurological time to respond), but we cannot know how I will respond unless we finish the computation. It's a sort of catch-22 that prevents our algorithm from working in this situation. There's nothing inherently wrong with our model; it just can't converge to a solution in certain regions of the universe because of the above problem. So in summary, your thought experiment doesn't disprove the possibility of a deterministic model per se. Rather it demonstrates (roughly) that any such deterministic model will have limitations in its range of application, though there should still be places where it functions perfectly. As a final disclaimer, note that all this is heavily related to much more concretized problems in the study of differential equations. That is the field of mathematics (and physics) which deals with precisely the question of how states evolve over time. 1 answered Jun 11 '14 at 16:15 commando 6,08566 gold badges3232 silver badges6666 bronze badges I think you've essentially rediscovered the undecidability of the Halting Problem. This is the statement that it is impossible to write a program that can determine whether any program will terminate. The actual proof uses some rather involved logic, but the result can be summarized by the following counterexample: write a program that takes the output of a hypothetical Halting program when run on itself, and terminate if and only if the Halting program predicted that the program would not terminate. This contradicts the Halting program, therefore such a universal program cannot exist. Within the context of a model for the universe, my hypothetical explanation deals with how such a model would have to work. Suppose that we know a deterministic model for the universe, and from this construct a function called `Predict10`. This function takes any complete `state` as input and returns `newState`, which is what `state` is predicted to evolve to in ten seconds. `Predict10(state) = newState` Note that each state consists of many many points spread out across whichever (closed) system you're running the model on. `Predict10` will function by applying the rules of the model to each point in `state`, taking into account every other relevant point. Essentially each point in `newState` is determined by a (presumably very complicated) series of equations operating on `state`. Let the current state of this very universe be `thisState`, and let `nextState = Predict10(thisState)`. Suppose we look at the Andromeda galaxy in `nextState`. The state of every point in the Andromeda galaxy will be determined by the aforementioned equations derived from our model. Of particular note is that, since the Andromeda galaxy ten seconds into the future is not in our (the observers') light cone, the fact that we use `Predict10` at `thisState` can have no bearing on `nextState` in Andromeda. That is, our use of `Predict10` is not part of the equations used to determine Andromeda in `nextState`. Thus we cannot "interfere" with the deterministic model's results for Andromeda, and the equations should converge to some reasonable answer yielding Andromeda ten seconds in the future. Now, instead suppose that we want to look at the state of my computer in `nextState`. Here is where we run into a problem. Take any point in my computer, and consider the equations that go into determining its `nextState`. Part of these equations will be the fact that I use `Predict10`, since the point is in that event's light cone. However, the point is also in the light cone of my response to the result of `Predict10` - and there's the rub. We need to know how I will respond to `Predict10` in order to finish computing `Predict10` for any point in my light cone (beyond points that take place before I've had sufficient neurological time to respond), but we cannot know how I will respond unless we finish the computation. It's a sort of catch-22 that prevents our algorithm from working in this situation. There's nothing inherently wrong with our model; it just can't converge to a solution in certain regions of the universe because of the above problem. As a final disclaimer, note that all this is heavily related to much more concretized problems in the study of differential equations. That is the field of mathematics (and physics) which deals with precisely the question of how states evolve over time.