Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now
2 added 294 characters in body
source | link

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
source | link

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.