Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 :-)

share|improve this question

closed as not a real question by Qiaochu Yuan, fedja, Loop Space, Reid Barton, Scott Morrison Apr 21 '10 at 20:46

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
I have no idea what "infinite CPU clock rate" is supposed to mean. As in your other question, you are mixing mathematical ideas with your own intuitions, and that's the ultimate source of your confusion. Whether a mathematical idea is valid or invalid is independent of your intuition: when they come into conflict, it's your intuition that needs to be corrected, not the idea. You should read some books on set theory. –  Qiaochu Yuan Apr 21 '10 at 9:38
    
Here is a possible salvage of this scenario: the phrase "infinite storage" makes it very unclear what kind of variable A is, but some sense can be restored if A is allowed to be the cardinality of some set S and "infinite CPU clock rate" is interpreted as "add countably infinitely many elements to S every second." Then, in fact, the cardinality of S stays the same as the cardinality of the natural numbers at every finite time. This is a standard exercise in basic set theory. –  Qiaochu Yuan Apr 21 '10 at 9:42
    
I still really don't know what you mean by "infinite CPU clock rate." When you say things like that, you confuse finiteness of "real time" with finiteness of "CPU time" and you seem to be switching between the two concepts in your post; that might account for some of your confusion. You need to think hard about what you want this to mean (if you want it to mean anything at all). –  Qiaochu Yuan Apr 21 '10 at 9:44
    
Thanks, Yuan. Infinte clock rate just means it executes a infinte number of cycles in any finite time. An infinite register is just a Hilbert hotel. A starts out like ..00000001. Then A = ..00000010. Next A = ..0000011 etc. What is difficult whith this? The point is that A can NEVER become infinte (not even at infinte clock rate) since there is no finite A such that A+1 = infinte Thanks, Carl –  Carl Apr 21 '10 at 10:49
    
Closed. You've received some good looking answers, but unfortunately that doesn't redeem the question. –  Scott Morrison Apr 21 '10 at 20:48

3 Answers 3

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.

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, published in Minds and 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. See the ArXiv version.

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 Δ12 in the descriptive set-theoretic hiearchy, and had led to a rich structure theory there.

share|improve this answer
    
Thanks a lot Joel. I'll certainly have a look. Best, –  Carl Apr 21 '10 at 11:19

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$.

share|improve this answer
    
Thanks Douglas. I still don't see how A (which still increment 1 for each loop) become infinte since there is no finte A for which A+1 is infinte. Remember A starts out finite. Best, Carl –  Carl Apr 21 '10 at 10:53

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 − 2k | 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.

share|improve this answer
1  
Peter Koepke and Russell Miller have analyzed a register machine version of infinitary computation (see springerlink.com/content/2k27k5jlu33j3406, and there are many other articles). Russell Miller and I, for example, solved the analogue of Post's problem for ordinal register machines: qcpages.qc.cuny.edu/~rmiller/Post.pdf –  Joel David Hamkins Apr 21 '10 at 12:56
    
Thanks again everyone. I guess the real problem is that I've been taught that for any finite A, A+1 is still finite and the set of finite integers is inexaustable (is that word right?). So how does a finite A become A+1 = "omega" ? Best, –  Carl Apr 21 '10 at 13:08
    
The thing is that there isn't a value of A for which A+1=omega. The register value of omega arises as the limit of an infinite number of incrementations. In the Zeno model I outline above, there isn't a value which A has "just before" t=1, for which omega is the next largest value; instead, the value of omega at time t=1 arises because it is the smallest ordinal which is larger than all the values that A has before t=1. Taking the limit of a finite number of incrementations, but then making the number of incrementations arbitrarily large, yields the limit omega. (Look up "limit ordinals".) –  Niel de Beaudrap Apr 21 '10 at 13:27
    
Also, because you ask: the word is "inexhaustible", with an 'h'. (-: –  Niel de Beaudrap Apr 21 '10 at 13:27
    
Thanks a lot Niel. I'll let it digest for a while. Not sure if I fully understand yet. Still a lot to learn I see. Best, –  Carl Apr 21 '10 at 13:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.