Multiple levels of infinity

Question

Some programmers don't see much relevance in theoretical CS classes (especially my students). Here is something I find very relevant. Let me build it up in pieces for those that haven't seen it before...

A) Programming problems can be reworded to be questions about languages.

B) Turing machines recognize languages.

C) Turing machines can be encoded as (large) integers.

D) Therefore, the number of possible Turing machines are countably infinite

E) The power set of a set is just all the possible subsets of that set.

F) If a set is countably infinite, its power set is bigger, ie, uncountably infinite.

G) Therefore, if a language is infinite, it has an uncountably infinite number of subsets. Each of these represents a problem. But there are only countably many Turing machines with which to solve those problems. And if we cannot solve a problem with a Turing machine, it cannot be solved.

Conclusion...we can only solve an infinitesmally small fraction of all problems.

My question is almost here...

Whenever I present this argument to students, they get stuck on the countably vs. uncountably infinite. They generally do not have strong math backgrounds, so attempts to explain via Cantor's diagonalization argument tends to glaze their eyes.

Usually I try to give them somthing they can grasp, like this...place a finite box over any portion of the counting number line, and we capture a finite quantity of those numbers...but place a finite box over any portion of the real number line, and we capture an infinite quantity of real numbers. A sort of evidence that there ARE more real numbers than there are counting numbers.

Finally my question...How do YOU explain the concept of multiple levels of infinity to those that have never heard of the concept, and may not be mathematically inclined?

Final Edit: I learned a lot by asking this question and I appreciate the feedback. I wasted far too much time trying to figure out what "Community wiki" actually was. I learned there is an inherent bias in some people against theory questions that I feel is simply a mistake because so much of what we do today was theory yesterday. But this bias is natural and while I disagree with them on the value of theory, I have no problem with it, and it helps me understand where my students are coming from. I do think the BS comment was unnecessary.

I do not feel this question was a poll or a preditions-for-2009 question at all. Those of you that only want coding questions with coding answers might want to re-examine that requirement. I have moved this question to community wiki but strongly feel I was compelled to do so by improper use of force.

Answer 1

Forgive the poorly written metaphors below.

I personally think of the countability/uncountability dichotomy as being very closely related to Zeno's paradox of the arrow.

The set of all natural numbers is countable, there is a specific method of generating the "next" integer, and it will get you a step forward. Countable sets are forward-moving in that sense. It's almost as if it has a velocity, it keeps moving forward.

---

The set of all real numbers is uncountable, like zeno's arrow.

If you have to move between the origin (0) and the destination (1 == 2^-0), you must first go through the midpoint (1/2 == 2^-1).

Now your destination is 1/2; If you must then go between the origin (0) and the (1/2), you must go through the midpoint (1/4 == 2^-2)

So on and so forth, so to get between 0 and 1, you must first get between something inbetween, which you must first get between something inbetween. There is no finite method of calculating the "next" step, so the velocity (in contrast to the velocity of natural numbers) doesn't really exist, your next step is not going to take you anywhere.

Edit:

I realize now that this probably has to do with the total ordering and mapping of the set of natural numbers to any countable sets. If you can't totally order the items in a set, or you can't create a method to determine what the next item is in a set, chances are it's uncountable.

Answer 2

I think your explanation is the simplest, as that is what I learned. It's almost as if real numbers have multiple dimensions of infinity. It is infinite in one direction, but also in another.

Diagonalization is a very cool experiment, but I can see how it may go over beginners heads. It does make sense though, if it is demonstrated in a very deliberate way, going very slowly. Just throwing up numbers quick can be hard to follow I imagine.

I think the principle of Cardinality of the Continuum is also helpful, although perhaps can be simplified to a beginner level. Showing that there is more beyond simple real vs. integers can potentially help something to 'click'.

Answer 3

Where's the "very relevant" part?

Edit: OK, I've been writing code professionally for 13 years and I wouldn't call levels of infinity relevant to anything I've ever worked on.

And I guess I would draw a different conclusion from your theory. How is "we can only solve an infinitesimally small fraction of all problems" the limit of our craft?

Sounds to me like there are an infinite (countable or uncountable doesn't seem to make a difference) number of problems. Therefore our craft is unlimited -- we will never run out of problems to solve.

Answer 4

Programmers (or at least, myself) don't often have to worry much about infinity in this way. When you place a finite box over any portion of the machine-representable real number line, you get a finite quantity of real numbers. =)

For example, a double precision variable has a finite number of possible values: 2^64.

Answer 5

There are serveral tens of thousands of words in the English language. You can count the number of words in a book or the number of books in the universe. You cannot count the number of books that will ever be

Answer 6

Conclusion...we can only solve an infinitesmally small fraction of all problems.

You must be web designer.

Answer 7

Here's an example of a computable problem: at the start of a chess game, is it possible for white to force a win?

The number of possible moves and counter-moves is finite. All we have to do is build the trees and prune them. We haven't done this yet only because with current technology it would take billions of years.

Here is an example of a problem that is not computable: Given a two-dimensional view of a scene, construct a full three-dimensional model of the scene.

We do this all the time. (Make a room with a peephole in the door. Have someone furnish it. Look through the hole and describe everything you see.)

We do not compute the incomputable. We produce an approximate result (just like we compute and use an approximate value of pi, another incomputable number). We keep updating the result as more information comes in. That's what optical illusions are all about. When you look at the picture of "a vase, or is it two faces?" your visual system says "It's a vase. No. Wait. It's two faces. No. Wait. It's a vase." You see it switching back and forth between the two interpretations.

Just because something is not computable is no reason not to do it.

Answer 8

G) Therefore, if a language is infinite, it has an uncountably infinite number of subsets. Each of these represents a problem.

Citation needed. You can't merely assume that any (possibly infinite) set of Turing machines necessarily represents a distinct 'problem'. At the very least, you have to (separately) formalize the definition of 'problem' as much as Turing machines have been formalized.