Principia

I think we are all dancing around the issue of what it means to 'describe' or to 'name' a number. lpetrich actually brings up an interesting issue with regards to obs. (2) since it invokes Turing's halting problem. Consequently, in answering this question it seems that we also have to define whether or not a description 'decidedly' describes a number. For instance, is the description of 'pi' as the ratio of the cirumference of a circle to its diameter more preferable than its representation of the sum of some infinite series? Another interesting problem is that in creating a description of a number, wouldn't someone need to 'know' the number by an independent means? Otherwise, how do we know that the number being described isn't already described in another fashion? One approach is to categorize all independently describable numbers. But then does that argue for the countability of descriptions?

OK... so much for weekend musings.

[ December 07, 2002: Message edited by: Principia ]</p>

wade-w

I don't think that we need to be concerned about whether a given description is unique. The question is whether there is at least one such for any arbitrary real.

Bloop

What if I constructed a sentence like this:

This is the real number r.

Where r could be any real number.
Would that give me an uncountable set of sentences?

Principia

wade-w, I guess my point is whether or not this last question of yours is decidable algorithmically. How can you decide that an algorithm, f, for generating descriptions is surjective onto the set of reals?

[ December 07, 2002: Message edited by: Principia ]</p>

lpetrich

That would indeed produce an uncountable set of sentences, but nearly all of them would have infinite length. It's the set of all finite-length sentences that is countable.

Also, the numbers that can be calculated with a finite-size algorithm were first noted by Alan Turing as the "computable numbers"; there are countably many of them, meaning that most real numbers are uncomputable.

Jesse

Principia:
I think we are all dancing around the issue of what it means to 'describe' or to 'name' a number.

Well, my earlier post outlined a sort of "describable numbers paradox", the "paradox" being that one argument would suggest there are uncountably many real numbers with finite descriptions, while another argument (a stronger one, I think) suggests there are only countably many. The origin of the paradox seems to have something to do with the fact that ordinary language is both more powerful but also more ambiguous than formal languages like Turing machine codes. A central part of this ambiguity is that the notion of a number being "describable" in ordinary language is itself quite ambiguous, since there is no formal way to decide whether a given ordinary-language description is sufficiently unambiguous to uniquely pick out a particular real number.

In a way this is reminiscent of Godel's theorem, which showed that any system of formal rules for deciding statements about arithmetic will be incomplete, because there is a procedure for constructing a statement G that we can see is true but which we also see cannot be proven by the formal system. Since the argument that it's true cannot be stated in terms of the formal rules, we must use ordinary language to show why the statement must be true even if it's not provable (the argument is that we can show the statement G is equivalent to the statement 'G cannot be proven by this formal system', so as long as the formal system is sound, it cannot prove it without creating a contradiction--which means the statement itself must be true!)

But this doesn’t mean Godel’s theorem can’t be described within a formal system—it’s just that to show that the statement G for a formal system A is unprovable by A, you need to work within a larger formal system A’ which includes A, and then A’ will have its own Godel statement which is unprovable without moving out into a still larger system, and so on. So for the fully general statement that all formal systems are incomplete you need a verbal argument.

In much the same way, any well-defined description of a unique real number in ordinary language can also be shown to be describable within some formal language. Earlier I considered the diagonalization of the list of all possible Turing machines, which is a well-defined number but cannot itself be described as the output of any Turing machine. However, Turing also came up with the notion of an "oracle machine", which can perform all the elementary operations of a Turing machine with one addition: at any point in the computation, it can also submit the code for a Turing machine to a mysterious "Oracle" which returns a one-bit answer about whether that Turing machine "halts" or not. The halting problem refers to the fact that some computations will eventually stop (example: start with the number one, keep adding one until you get a number larger than 10, then stop) while others will go on forever (example: start with the number three, keep adding one until you get a number smaller than two). The question of whether an arbitrary Turing machine halts or not is something that cannot be decided by any one Turing machine; in general, the only way to know if a Turing machine halts is to actually run it, and if it does halt you’ll know in a finite number of steps, but if not you can never be sure that you just haven’t run it through enough steps yet. Of course, for some non-halting Turing machines like the one I mentioned above you can prove it won’t halt, but again, no algorithm will be able to decide if an arbitrary Turing machine halts. So, the "Oracle" used by an oracle machine is somewhat mysterious, and such a machine may be physically impossible in our universe; but still, we assume each possible Turing machine either halts or it doesn’t, whether or not we can ever know the answer, so naming a particular oracle machine should serve as a finite description of a unique real number, even if we can never know what its digits actually are.

In my last post I said that you could come up with a finite description of a real number that’s not the output of any Turing machine by considering the diagonalization of the list of all Turing machine outputs which correspond to real numbers. However, not all Turing machines will point to particular real numbers, because some will fail to come to a decision about what a particular digit of the output should be (consider a program that tells you "if the first digit is a 1, change it to a 0; if the first digit is a 0, change it to a 1). So to figure out which Turing machine programs correspond to computable real numbers, which you need to do if you want to diagonalize the list of computable reals, you have to be able to solve the halting problem. That’s why the diagonalization of the list of all computable numbers is not itself computable, but an oracle could "oracle-compute" it (Turing machines do computations, I’m not sure if there’s a corresponding word for oracle machines but since I don’t know it I’m making something up).

Since each possible oracle machine has a finite set of possible operations it can do, just like a Turing machine, it should also be possible to encode oracle machines as symbol-strings within some formal language, and list them all. But then, what about the diagonalization of this list? Well, what I’ve been calling an oracle-machine is really just what’s known as a "first-order oracle machine"; you can also have a second-order oracle machine which can consult an Oracle to decide if any first-order oracle machine halts, a third-order oracle machine which can decide if any second-order oracle machine halts, and so on. And you don’t even have to stop at finite-order oracle machines. Consider a list of "all finite-order oracle-computable real numbers"—we know it is possible to list all ordered pairs of integers (n,m) (see <a href="http://mcraefamily.com/MathHelp/CountingRationalsSquareSpiral1.htm" target="_blank">this</a> page), so we could construct a similar list which included every real number describable as the output of the nth m-order oracle machine (throwing out the negative numbers and treating a Turing machine as a zeroth-order oracle machine). How could we formally describe the diagonalization of this list? Well, for this you’d need to know whether arbitrary finite-order oracle machines halt, so we can define an omega-order oracle machine which can do this (in set theory, the set of all finite numbers is called omega). Again, it would be possible to come up with a code to express all possible omega-order oracle machines as finite symbol-strings, and then by diagonalizing you could come up with yet another real number not describable within this code but that would be describable within a set of codes for all possible omega-plus-one-order oracle machines, and so on.

To come back to my original point, although in my earlier post I talked about natural-language-describable reals vs. formal-language-describable reals, in fact any real you can describe clearly in natural language can always be described in some formal language (the set of codes for some type of oracle machine), but the diagonalization of the set of all real numbers describable within this formal language will require going to a higher formal language (codes for a higher-order oracle machine). And there is no end to the "orders" of oracle machines; for those who are familiar with a bit of set theory, we can say that there is a new level of oracle machine for each countable ordinal number, of which there are uncountably many (see <a href="http://216.239.37.100/search?q=cache:yi8h8_3J4D4C:www.math.hmc.edu/funfacts/ffiles/30003.8.shtml" target="_blank">this</a> page, along with <a href="http://mathforum.org/library/drmath/view/52423.html" target="_blank">this</a> one, for more on the infinite ordinals; Rudy Rucker’s <a href="http://www.amazon.com/exec/obidos/ASIN/0691001723/internetinfidelsA/" target="_blank">Infinity and the Mind</a> is also good if you want more info). However, in a way this just opens a new can of worms, since it may not be true that all the countable ordinals have finite descriptions themselves. But I’ll stop here, I’ve probably confused people enough (a clearer discussion of Turing machines, the halting problem, and oracle machines can be found in Penrose’s two books—<a href="http://www.amazon.com/exec/obidos/ASIN/0192861980/internetinfidelsA/" target="_blank">The Emperor’s New Mind</a> and <a href="http://www.amazon.com/exec/obidos/ASIN/0195106466/internetinfidelsA/" target="_blank">Shadows of the Mind</a>—although I don’t agree with his views on the implications of this stuff for A.I. and the nature of the mind).

[ December 07, 2002: Message edited by: Jesse ]</p>

wade-w

A Dedekind Cut is a partition of an ordered field (A,B) such that A is closed downwards and has no maximum, and B is closed upwards. This concept is often used to construct the reals from the rationals by considering Dedekind Cuts of the rational numbers. For example, sqrt 2 can be defined as A = { a in Q : a^2 &lt; 2 or a &lt; 0}, B = {b in Q : b^2 &gt;= 2 and b &gt; 0 }. We can then describe any possible real as a Dedekind Cut on the rational numbers. In fact, one of the most common definitions of the real numbers is the set of all Dedekind Cuts.

Note: The definiton for Dedekind Cuts I gave above is more general than others you will find. Some sources will define a cut as I did above, and then call a cut on the rationals a Dedekind Cut. I have seen other variations in terminology as well, for instance when the no maximum requirement is added to the mix.

Edited to add: I'm kicking myself for not thinking of this sooner, but its been a long time since those analysis courses.

[ December 09, 2002: Message edited by: wade-w ]

[ December 09, 2002: Message edited by: wade-w ]</p>

Answerer

I have an question, since our mathematical tool is incompleted, will it created some 'hidden problems' in our understanding of the universe?

Thomas Metcalf

Obviously, I should have paid more attention to this thread.

My (rather uninteresting) point is that because there are more real numbers than English (or any formal symbolic) descriptions, there are some real numbers we'll never describe. Not that never can be described; any particular real number is describable in principle, I think. It's just that no matter how much writing or talking or anything we do, there are some real numbers that will forever be beyond us. We'll never get to all of them, even given an infinite time.

Other posters have been correct in that I take the way to produce a denumerable set of English descriptions is something like Gödel numbering. So if the set of English descriptions is denumerable, and the continuum is greater than the set of descriptions, there are some numbers that don't match any English or formal symbolic description. So it is not the case that for every real number, there is an English or formal symbolic description.

I'm getting into this a little late, so I hope I haven't missed much. Anyway, as for the question of whether there are numbers we'll never be able to know, I think it simply follows from the fact that there are numbers we'll never be able to name. What does it mean to "know" a number? As far as I can see, it means to formulate a description.

wade-w

I agree with you in that the set of all possible names for numbers, in any possible formal name scheme is at best countable. And since the reals are uncountable, there is no way we can ever have a unique name for every real number. Jesse's excellent arguments show this conclusively.

But as I showed in my last post, this does not mean that we can not find an unambiguous way to derive all of the real numbers, and in this sense we can know all of them. Otherwise, we would never be able to be sure that this thing we call R really exists (Well, I guess this is mostly true of constructionists, but the rest of us would still have to be a little worried). What I outlined above is one of the two most common ways to rigorously construct the real numbers from Q. Historically, it was also the first one to be developed.

Given any arbitrary Dedekind Cut, if the least upper bound of A is a member of B, then the Cut defines a rational number, namely that least upper bound. If however, it is not in B, then the Cut defines an irrational. And in fact, the set of all Dedekind Cuts is identical to the whole set of real numbers. It is not easy to see, I know, how this can overcome the uncountablity question.

The other common formulation is perhaps better for this, but it involves Cauchy sequences, and the notation would get almost impossibly unreadable in ascii. One step in this construction involves taking the power set of a countably infinite set, and thus the set we operate on is uncountable.

Either way, I would argue that since we can construct the reals formally, it is therefore possible to know all of them, even if we can't name them all.

I think that in the end, this is a philosophical issue. I fail to see the essential difference in saying that we can describe any arbitrary real, and saying that it is therefore possible to describe all of them.

[Edited to delete stupid argument based on the axiom of choice. I need to start thinking a little more clearly before I post things like that!]

[ December 10, 2002: Message edited by: wade-w ]</p>