UNLV CS 456/656 Does Infinity Exist?

University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 456/656 Does Infinity Exist?

Revised November 1, 2005

In response to the challenge, "I don't believe infinity really exists," I am posting a number of answers.
An answer from the University of Toronto Mathematics Network.
Wikipedia definition of infinity. Filled with lots of links.
Let me give an answer that is specific to our course.

The machines we deal with in CS 456/656 are not physical machines. They are abstract machines, which means they are mathematical objects, just like the integer 2, or the integer 2^1000000. Do you claim that 2 does not exist? Do you claim that 2^1000000 does not exist? I suppose there are people who would say that the number 2 exists, but that 2^1000000 does not exist, since there is no set in the universe with that many elements. If you say that, then, of course, you win, there is no such thing as infinity.
But if you admit that 1 exists, and if you admit that if an integer exists, its successor (i.e., the next integer) exists, then you are forced to admit that 2^1000000 exists. If all those integers exist, then you have, effectively, admitted that an infinite set (the set of all positive integers) exists.
But wait ... what about time? You could defeat that by saying, "If I start counting, then all the numbers I reach exist, but there will be a last number I reach before I die, and there is no reason to believe that those beyond that exist." Or maybe, instead of counting, you are squaring them.
What about a sequence with a recursive successor rule? That means a sequence of objects (let's say integers) x₁, x₂, ... where there is a rule (a recursive function) which allows you to compute x_n+1 from x_n. You could argue that the sequence cannot be infinite, for the same reason as above: you never finish in your lifetime, or for that matter, in the lifetime of the universe (if the universe has a finite useful lifetime, which is generally believed). The answer to this question is simple: a sequence is a mathematical object, which may or may not have a physical implementation.
Similarly, a Turing machine is a mathematical object, a configuration of a TM is a mathematical object, and a computation of a TM is a mathematical object, namely a sequence of configurations. To say that a TM "runs forever" is a bit like saying "the tree wants to spread its seeds." The tree doesn't "want" anything, in the human sense. To say that is to model the tree's actions in terms of something that we understand better.
And the TM does not operate in time, in the physical sense of time. that we're familiar with (i.e., seconds, years, etc.). To say that it runs "forever" is merely to say that the sequence of configurations is infinite, just like the sequence of prime numbers. (What is the "time" of the prime number 107?) Can a physical machine be modeled by an abstract machine? Probably. Can an abstract machine be modeled by a physical machine? Probably not.