**Problem Detail:**

This may get slightly philosophical, but consider the following program:

`bool lampState = false; TimeSpan timeout = 1; while (true) { lampState = !lampState; Thread.Sleep(timeout); timeout = timeout / 2; } `

DotNet Fiddle link for C# code

This is obviously an implementation of Thomsons lamp in C#.

So the question is what is the value of lampState after 2 seconds of execution?

Lets assume that no physical law prevents us from constructing an infinitely fast computer. Static code analysis shows that we will never exit the while loop. Does this mean that we can have an algorithm that is arbitrary fast, but not infinitely fast, not even theoretically (because we run in to a contradiction?

###### Asked By : Eiver

#### Answered By : Kilian Foth

No, it doesn't mean that.

The problem with Thompson's lamp is that a particular state of an abstract machine is not well-defined. This is nothing unusual. E.g., dividing by 0 also yields an undefined value, because any value we could choose would lead to inconsistencies with *other* definitions that we would like to keep - at any rate, more than the isolated, unimportant definition of 1/0.

Abstract machines can be implemented in real machines, but there are limits; one if them is that you have only finite matter, space and time available. Therefore, infinitely fast machines, just as infinitely big machines, *cannot* be implemented. This merely means that we cannot check the question by physical experiment.

There are many other machines that are infinitely large that we also can't build, but which at least yield a well-defined prediction (for instance, the machine that never does anything would leave the state at the initial value). Those machines cannot be tested by experiment, but they *can* be predicted theoretically. This machine cannot even be predicted, because it has been carefully defined to fall into an undefined niche of logics.

But this has nothing to do with the question how fast an algorithm can be. There are many algorithms of which we do not know whether (given enough time) they eventually terminate. Some of these may be testable by running them and waiting long enough, but since we don't know how long "long enough" is, physical experiment can only ever give the answer "yes", but never "definitely no".

Therefore you shouldn't be too worried about the fact that a certain machine can't actually be built. Some problems are better handled via experiment, and some via theory. Those that cannot be handled either way are vexing, but almost always they are far removed from any practical problem that we *really* need to solve.

Example: if mathematics weren't incomplete, i.e. it it **were** possible to determine the truth of any propositional formula via a single algorithm, mathematicians would be glad, but everyday life would not be much affected. Even knowing P = NP would do little; it is one thing to know that a prime can be factored in polynomial time, quite another thing to be actually able to do it.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48488

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback