Infinite CPU clock rate and hotel Hilbert

Question

Suppose we have a computer with infinte CPU clock rate, infinite CPU registers, storage etc. Lets run a program that could look something like this:

A=1 while A>0 A = A+1 repeat

We start the program in debug mode so we can stop the execution at any time and look at the value of A. Now, since the execution rate of the loop is infinte one could expect that the value of A becomes infinte at the moment execution starts. However, knowing that there is no finite number A such that A+1 becomes infinite, it is clear that A will remain finite for ever since A starts out as a finite number. So after running the program for any amount of time we will only observe a finite A. To avoid a paradox here, it seems that the concept of infinite execution rate must be impossible. But how?

So, as Hilbert starts checking in guests to his hotel, he naturally keeps adding up the number of guests that has checked in. He sees that no matter how fast he checks in guests and no matter how long he keeps checking in guests, he will always only have a finite number of guests.

Or..?

Best, Carl (math student :-)

Answer 1

What you are describing is a supertask, or task involving infinitely many steps, and many curious examples of these have arisen in mathematics, philosophy, physics and elsewhere. Perhaps the first would be Zeno's paradox. When one adopts a serious analytic attitude and makes a supertask problem precise---which you haven't really yet done in your question, and this explains the downvotes---then the paradoxical aspect evaporates and what remains is often an interesting bit of infinite combinatorics. Let me illustrate with an example, taken from an article of mine of infinite time Turing machines: Infinite Time Turing Machines: Supertask Computation (published in Minds and Machines).

In a more entertaining example, let’s suppose that you have infinitely many one dollar bills (numbered 1, 3, 5, . . .) and upon entering a nefarious underground bar, you come upon the Devil sitting at a table piled high with money. You sit down, and the Devil explains to you that he has an attachment to your particular bills and is willing to pay you a premium to buy them from you. Specifically, he is willing to pay two dollars for each of your one-dollar bills. To carry out the exchange, he proposes an infinite series of transactions, in each of which he will hand over to you two dollars and take from you one dollar. The first transaction will take 1/2 hour, the second 1/4 hour, the third 1/8 hour, and so on, so that after one hour the entire exchange will be complete. The Devil takes a sip of whiskey while you mull it over; should you accept his proposal? Perhaps you think you will become richer, or perhaps you think with infinitely many bills it will make no difference? At the very least, you think, it will do no harm, and so the contract is signed and the procedure begins. How could the deal harm you?

It appears initially that you have made a good bargain, because at every step of the transaction, he pays you two dollars and you give up only one. The Devil is very particular, however, about the order in which the bills are exchanged. The contract stipulates that in each sub-transaction he buys from you your lowest-numbered bill and pays you with higher-numbered bills. Thus, on the first transaction he accepts from you bill number 1, and pays you with bills numbered 2 and 4. On the next transaction he buys from you bill number 2 (which he had just paid you) and gives you bills numbered 6 and 8. Next, he buys bill number 3 from you with bills 10 and 12, and so on. When all the exchanges are completed, what do you discover? You have no money left at all! The reason is that at the nth exchange, the Devil took from you bill number n, and never subsequently returned it to you. So while it seemed as though you were becoming no poorer with each exchange, in fact the final destination of every dollar bill in the transaction is under the Devil’s ownership. The Devil is a shrewd banker, and you should have paid more attention to the details of the supertask transaction to which you agreed. And similarly, the point is that when we design supertask algorithms to solve mathematical questions, we must take care not to make inadvertent assumptions about what may be true only for finite algorithms.

That article contains several other entertaining supertask examples.

Specifically in the realm of computation, one can give a completely rigororous treatment of computations involving infinitely many steps. The theory of Infinite time Turing machines, for example, extends the operation of ordinary Turing machines into transfinite ordinal time, and has led to a rich subject. The article I link to above provides a lighter account of infinite time Turing machines and includes several fun examples of supertasks in physics and philosophy. The main reference for infinite time Turing machines is my paper with Andy Lewis in the Journal of Symbolic Logic, 65(2):567-604, 2000, doi:10.2307/2586556, (arXiv:math/9808093).

The basic idea of infinite time Turing machines is to extend the operation of an ordinary Turing machine into transfinite ordinal time. In the finite time context, when a machine fails to halt, we usually think of that as a kind of garbage situation, but actually, the machine might have been writing something very interesting on the tape, such as all the theorems of mathematics, and so we would like somehow to preserve that information into the limit. The infinite time Turing machines do so by defining the time ω configuration of the machine in such a way to preserve as much of the earlier computation as seems possible, and then allow the machine to continue computing to time ω+1, ω+2, etc. through all the ordinals. It turns out that the resulting computability theory lies at the level of Δ¹₂ in the descriptive set-theoretic hiearchy, and had led to a rich structure theory there.

Answer 2

Let $x(t)$ be the current state at time $t$ and $s=dx/dt \rightarrow \infty$ be the speed of the CPU. For all $t>0$ we have $\lim_{s \rightarrow \infty} x(t)=\infty$ and $\lim_{s \rightarrow \infty} x(0)=1$. So the pointwise limit can be described as the step function \[x(t)=\begin{cases} 1 & t=0 \\\\ \infty & t>0 \end{cases}\] which describes the output of your infinite computer at time $t$.

If you take infinitesimal time, you're essentially differentiating $x$ at $t=0$ (which is silly, since the function is not continuous). That is, it's essentially taking $0 \cdot \infty$.

Answer 3

Joel David Hamkins gives a good reference, which you should read. I will instead focus on describing the pitfalls of different notions of "infinite processor speed".

The question hinges, as Qiaochu notes in the comments, on what precisely you mean by "infinite clock rate". And also what it means to potentially perform an infinite number of increments, which would clearly occur if the computer performed an increment once every clock cycle, if that clock cycle were infinitesimally breif. As such things are physically impossible,* it becomes important to explicitly describe (in well-defined terms) what you mean by these ideas.
_{[ * in accepted models of physics, and in models of physics satisfying common constraints, e.g. of physical systems having a finite amount of energy ]}

As for performing an infinite number of increments: I would suggest that what your registers would have to store are ordinals (or some related type of data), so that the operation of incrementing possibly an infinite number of times is well defined, no matter what. (At the very least, the clock register will have to be an ordinal, as all it does is increment once every "clock cycle"; and we want the clock register to have a well-defined value at all times. For that matter, your register A may as well itself be the clock register.) Given this assumption, let's talk about clock speeds.

We need, for the sake of concreteness, to determine at precisely which times the clock register is incrementing: that is, those times t such that the value of A at any time t' > t is larger than at time t, because the instruction A = A+1 is carried out at time t. We must declare --- as a part of specifying the processing speed --- a subset S ⊆ ℝ which represent the set of instants at which the clock register increments.

There is a problem if you want your computer to have a "uniformly fast" infinite processing speed. This means that between any two points in time (modeled here by the real numbers ℝ as is usual), an infinite number of operations are performed. That is, there is always an element of S, and in fact infinitely many, between two distinct real numbers.^† The problem is the following: for any element of S, there cannot be such a thing as the "next largest" element of S; because (exactly as we noted just now!) for any s ∈ S, and for any supposedly "next largest" s' ∈ S, there is an element of S which comes between s and s'.
_{[ ^† That is to say, S is dense in the real numbers.]}

A consequence of this is that if the computer processing speed is "uniformly" infinite, the register A can never have the value 2! For even though we know that it starts at 1 at time zero, there is no "next" time that it increments; so there is no time at which A changes from 1 to 2. If it is supposed to take values larger than 2, but we cannot identify a time at which it had the value 2, it seems to me that this model of computer is ill-defined.

We can solve this if we abandon the idea of being uniformly fast over time. Instead, we may consider a Zeno computer: a computer which performs its first instruction in 1/2 second, its second instruction in 1/4 second, its third instruction in 1/8 second, and so on halving the execution time so that it performs a (countably) infinite number of instructions in 1 second. (You can then repeat this scheme every second, or some elaboration of this perhaps.) The point being that each instruction takes a finite amount of time, but that finite amount may be arbitrarily small, and there are intervals of time in which an infinite number of instructions are performed. What will then occur in this computer is that the register A is a function of time t as follows: it will be equal to

• 1, if 0 < t ≤ 1/2;
• 2, if 1/2 < t ≤ 3/4;
• 3, if 3/4 < t ≤ 7/8;
• ...
• ω (the smallest infinite ordinal), if t=1;
• ω + 1, if 1 < t ≤ 3/2;
• ω + 2, if 3/2 < t ≤ 7/4;
• ...
• ω⋅2, if t = 2;
• ω⋅2 + 1, if 2 < t ≤ 5/2;
• ω⋅2 + 2, if 5/2 < t ≤ 11/4;

etc. Note that at every integral t after zero, there is a value which A holds only for an instant, prior to being incremented again; this is a feature of our choice of how to define "when the clock register increments".

Then, the behaviour of the register A is clear; it increments at all times t ∈ S = { N − 2^k | N,k ∈ ℤ }, and in particular performs a countably infinite number of operations "just prior to" (i.e. in any finite amount of time prior to) every integral value of t. The value of A is then well-defined.

An important feature of the Zeno computer model, which makes it well defined, is that the limit points of S form a well-ordered set. This is in fact nothing more than saying that the values of the clock register A are ordinals (or always have a meaningful "next largest" value) and is well-defined at all times. In particular, there do not exist any convergent, strictly decreasing sequences in S. This feature is necessary for the clock register to have a well-defined value at all times; and this is the criterion that fails for "uniformly" infinite clock speed.