Showing posts with label Thomson's lamp. Show all posts
Showing posts with label Thomson's lamp. Show all posts

17 March 2015

A new kind of infinite machines

Since David Hilbert’s thought experiment, it is popular to demonstrate the strangeness of infinities describing a hotel with infinite rooms where new and new tourists/tourist groups arrives (even in a countably infinite number). The trick is that although all the rooms are full, the management always can find free ones – after rearranging the reservations. I.e. if only one tourist wants to check in, then the person occupying room 1 is can be moved to room 2; and the occupier of room 2 to room 3 etc. (and the occupier of room n moves to room n+1). If a countably infinite amount of new guest arrives, then the person from room 1 moves to room 2; the person from room 2 to room 4 (from room n to room 2n). After all, there as many odd as even numbers and the new visitors can occupy the odd-numbered rooms that are free now. This method works even if countably infinitely many buses arrives with countably infinitely many passengers on each.
The infinite hotel is misleading in a certain way, since it suggests that these algorithms are the simplest solutions for pairing the rooms and visitors. But there is a simpler method: at the time of the arriving of a new group with even countably infinitely visitors, we can ask every occupier to leave their room – the result is infinitely many free room with infinitely many persons (including the newly arrived ones) without room. Then we ask everybody to go into a still free places – and that’s all: we paired infinitely many persons with infinitely many rooms.
Keeping in mind the lesson of the infinite hotel, we can introduce a new kind of infinite machines with a new typology.
From our point of view, there are two fundamental parameters to determine these machines: the number of steps of the process to reach infinity and the needed time.
It’s obvious that there are impossible machines. You cannot build a machine that solve a problem in zero time even it infinitely fast; and similarly impossible that version that takes only finite number of steps in an infinitely long period – but not because it halts at a certain point in the process (i.e. since it is prescribed that it has to stop after a certain number of steps or reaching a number), but because – as a reversed Thomson lamp – its algorithm prescribes it.
So the simplest infinite machine is a Turing machine with an infinite tape – it can take infinitely many steps over an infinitely long period (and every step can be paired with the moment of the step).
Opposite to it, a Tomson's lamp takes infinitely many steps within a finite period of time. The solution is that 1+1/2+1/4…=2 so if we can press the Thomson lamp’s button two times faster at the n+1st step than at the nth step, then we can finish the process within 2 unit of time (i.e. within two seconds, if it took 1 second to press the button for the first time).
But it is possible a third type of infinite machine. Obviously, the last time we press the Thompson lamp’s button we have to do it infinitely fast, and the pressing process is infinitely short. It means on the one hand, that we handle (at least mathematically) an infinitely small amount. On the other hand: Why should we vary the pressing time to reach our aim? It is possible theoretically to press the button infinitely fast even for the first time; and even an infinitely small time is enough to do it infinitely many times. So this infinite machine finish its process not in infinite time (as a Turing machine) and not in a finite time (as a Thomson lamp), but in an infinitely short time.

machine type number of steps time
Impossible zero infinite zero
Impossible finite finite infinite
Turing infinite infinite
Tomson lamp infinite finite
Third type infinite infinitely small

23 February 2015

Thomson’s infinite lamp as a mathematical monster

Imagine that we have a lamp – it is switched off at its initial state and this state can be changed by pressing a button. Having been an hour to play with this lamp, we switch the lamp on after 30 minutes. Then after waiting for 15 minutes, we switch it off – and then we switch it on again exactly 7.5 minutes later – and so on. I think that the end of the story is self-evident: after one hour (and neglecting that it is physically impossible) we pressed the button infinitely many times.
But what will be the result? Will the lamp light? Or will not?
It seems to be an unanswerable question – after all, we can regard the switch off state as an “odd” and the switch on as an "even" number (or vice versa). The source of this problem is that only a natural number is either odd or even – but infinite is not a number in a traditional way.
But there is another analogy and it can help. Nobody knows PI’s exact value since it is an irrational number. What is more, according to our actual knowledge, its digits are randomly distributed. But if we would be able to compute all of its digits, would the last digit be an even number?
Perhaps it seems to be an acceptable answer that there is no a last digit of PI, so it is neither odd nor even. But PI is nothing more than the ratio of the circumference of a circle to its diameter and although we do not know exactly the numerical value of this ratio, it is a certain, existing value. Computing more and more digits of PI, we’ll know it more and more accurately – and computing it to the infinity, we’ll know it exactly.
Ad analogiam: if we press the button of the lamp infinitely many times, then the lamp will be necessarily either switched on or switched off – although we cannot predict the lamp’s state.
At this point we can distinguish to different types in math: random and compressible strings. The previous one means that we cannot find a representation of the given string which is shorter than the original one. Heads and tails is a good example for it: you won't know the result without tossing the coin in reality.
Or onecould mention the cellular automatons (CAs). The state of their cells depend on the neighboring cells’ states and a CA changes in discrete steps. The result is that although the system is absolute deterministic (certain starting configurations always results the same next phases), cellular automation is an incompressible process. We cannot compute the next phase without executing the program itself.
Opposite to these above mentioned examples, a compressible string can be regarded to be “regular” in a sense that if we know the rule, then we can find the nth digit without computing others.
Our lamp represents a totally different solution. We can compute its every stage and its algorithm is ridiculously simple, so it is compressible - except for its endpoint. We cannot answer whether the lamp is switched on at its final stage – unless we de facto pressed that button for infinitely many times.
I wonder whether there are other, strange categories – for example, who could imagine a string which is compressible only at its endpoint? Perhaps other mathematical monsters lurking somewhere.