You can't write that number; in fact, you can't write most numbers.

Yes that has always been awesome (in the literal sense) to me. All the numbers humanity ever could describe, ever, even to infinite time, are just a sprinkle on the number line.

"The number of programs for any effective computing device is countably infinite..." Prove it. OK, I'm not that lazy, I looked it up. Basically, all you need to know is that "finite computer programs can always be represented as a finite text file." Order the programs alphabetically... 1:1 mapping with the natural numbers... blah blah blah...

What if the program describing the number *isnt* finite, but can be described itself by a finite program? Like a genetic algorithm, for example.

Would that number count as undescribable, or would it simply open up a new class of describable numbers, or would they already somehow be included in your definition?

when explaining this to people i often like using a geometric example:
draw a line segment on a piece of paper, consider the length of that segment to be 1. if you put a point on that line, the length from that point to the end of the line will virtually always be an indescribable number.

What about numbers which are describable, but we don't know what the description is?

Consider the smallest even number >2 which is not the sum of two prime numbers, if there is such a number, or else 2. We know that 2 is describable, and we know that all even numbers are describable, so, in either case, that number is describable.

Re #3:

That's not an escape. It comes back to basic computation theory: if you could write a program that generates a program that does X, you can write a program that does X.

If you could write a program that could generate an infinitely long program that generated a number, you could bypass the middle step and just write a program that generated the number.

Re #5:

Doesn't matter. Knowing which numbers are describable, and knowing how many numbers are describable are two different problems. In terms of computation, it comes back to the good old halting program; you know that some programs will halt, and some won't - but you can't say which ones. But you can reason about properties of various subsets of programs, even if you can't always tell which programs are in which subsets.

I'm confused about pi. Where is the finite program that can compute the infinite digits of pi? Does it matter that such a program might need infinite memory to run or you don't consider memory a part of the program? All programs to compute pi that I know have some upper limit on the number of digits they can compute.

This isn't the best definition of describable to use. There are more general definitions. For example, I can describe in an intuitive sense a number in the following way:
List all possible Turing machines in some order (we can do that explicitly). Construct a number a as a having a 1 in the nth digit iff the nth Turing machine halts on the blank tape. This number is intuitively describable but is not describable under your definition.

A slightly more general definition which includes all of yours but requires more detail to be more precise is that the number can be uniquely specified in ZFC using a finite statement. The basic result still holds in this larger setting.

TomS, all *integers* are describable in the sense Mark's talking about here. (Whether or not we know what they are.) In particular, e.g., if you pick a formalization of number theory and a way to encode proofs therein as integers, then the integer corresponding to the shortest proof of Fermat's last theorem is describable, even though we'll never know what that is.

But a *real number* that there's no way to compute isn't describable in Mark's sense, although of course the fact that we don't know a way to compute a number doesn't mean that there isn't one.

Re #8:

There are a variety of ways to compute pi, mostly based on algebraic series. For example, see:

http://mathworld.wolfram.com/PiFormulas.html

Those formulations are all built on an infinite process, where each step gets you closer to the actual value of pi. Any of them can be implemented as a program that outputs a series of progressively better approximations of pi; further, any of them can be implement in a form which outputs individual digits of pi in sequence after they're sure that a given digit won't be changed by further steps.

Of course, we are talking about theoretical programs. You can't "output" an infinitely long representation without having infinite storage available. In the typical formulations of theoretical computers, you do have infinite storage available.

Re #9:

I *think* that we're still looking at the same basic definition. For the example that you used, we can generate that as the limit of the result of a computation. Take a turing machine whose first approximation is 0. Then it runs one step from program 0. IF that's "halt", it writes a 1 in position 0. Then it runs one from program one. Then one step from 0, one step from 1, one step from 2. Then one from 0, one from 1, one from 2, one from three. The usual diagonal structure used for iterating over all programs. As it adds machines to the sequence that it's iterating over, it sets their initial value to 0; if/when they halt, it writes a 1 in that position. The result of that process in the limit is the number you're describing. You'll never get it exactly, and you'll never know when a given bit has stabilized; but if it runs forever, it will generate the number. So the number is describable by a non-terminating finite program.

Or am I missing something?

'It doesn't matter whether that program ever finishes or not - so if it takes it an infinite amount of time to compute the number, that's fine - so long as the program is finite.'
That doesn't really make sense, because if the program doesn't terminate, it doesn't produce any description. I think it might be better to say that the program produces progressively better approximations, i.e. it is a computable number.

Another important distinction that should be made is the difference between computable and describable. E.g. your favourite number, Chaitin's Omega is definitely describable (i.e. provably there is such a unique number, under appropriate premises), but not computable.

What intrigues me about this whole thing is that all of mathematics really condenses into a finite set (at any given time there is only finite, if expanding, space for mathematical scripture), even though conventional theories contain all these uncountable sets.

#8: Try google: "program that computes pi". A kid taking computer programming for the first time can write such a program easily.

#4 brings up an interesting conundrum. Whereas by drawing a finitely long line on a piece of paper, and whereas you assume it to be of length one, and whereas you place a point randomly on said line, therefore the distance from the point to the end of the line is likely to be an indescribable number. Yet, by undertaking this procedure, you've just described it, symbolically and in finite space, by drawing a line with a dot on it.

True, the representation doesn't consist of decimal figures with which you can readily perform arithmetic with. Nonetheless, the space taken to represent the undescribable number is itself finite and expressed visually. In other words, it has a description.

Is "finite amount of space" the right criteria? This is very informal, but I could imagine a decimal expansion where each digit necessarily takes a larger and larger amount of space to generate, so the space requirements are effectively unbounded, but the amount of space needed to calculate the *next* digit is always bounded.

The key criteria in my thinking is the program "writing" the number (I can't help but think in terms of decimal expansions of pi, it seems) has to be productive - it has to always be able to generate some more of the number in a finite amount of space and time, but the amount of space required as the decimal expansion streams out could be arbitrarily large.

#15 I don't see this as a conundrum, but I could be wrong. What you describe is not a finite procedure for generating a particular number, it's a finite procedure for finding numbers in a range of numbers. In other words, it doesn't uniquely characterize any single number - the criteria for some number being describable is there is a finite procedure that allows for calculating that number.

But I don't know the theory behind this deeply, so this is, at best, informed speculation.

Finite amount of space refers to the length of the program, not the amount of memory it allocates.

Just use computable math and intuitionistic logic, leave all the other numbers and classical logic to the mathematicians.

No infinity, no problem.

#18 Aaah yes, must have misread that part of the post.

I think that I agree with #15 that we're ignoring the whole set of geometrical descriptions of numbers. For example, the geometric descriptions of Ï and â2 are rather trivial even though we can't get them exact without the ability to draw perfect circles or perfect right angles (much like the infinite algorithm that would be needed to express these numbers as complete decimals).

@Maya Incaand: Hear, hear. Too bad that the classic theories tend to be simpler. Though I've half a mind restarting Hilbert's program from Conway's surreal numbers.

#15, your idea reminds me of the story of an alien visiting Earth. The alien wants to take as much of Earth's culture and knowledge back with it as it can, but its spaceship is pretty small. The alien's solution? It takes all of the information that it's gathered, joins it into a huge binary file, then interprets it as a binary decimal expansion: 0.1011010110110001...

The alien then takes a carefully calibrated rod from its spaceship and trims it down so that it's a fraction of its old length equal to the number just calculated. The alien can now return home with all of Earth's knowledge.

Of course, this would quickly run into problems with physics. Assuming the rod was 1 m long to start with, the alien could record about 116 bits using this method before requiring sub-Planck length resolution. This also assumes that the universe isn't discrete. If there's an uncountable number of positions in space, just how many are there? Aleph_1? More than aleph_1? Beth_1? To quote Scott Aaronson, "We don't want the answers to "physics" questions to depend on the axioms of set theory!"

@mds
I think we don't want the answers to *any* questions to depend on the axioms of set (ZFC) theory!

Mark, yes you are correct that in this case they are the same. I'm not convinced that the definitions are the same. For example, if I had said instead of halts on the blank tape I had said "halts on all input tapes" then there's no obvious way to generalize to that question. Moreover, even with an oracle that answers the halting problem one cannot answer whether a given machine will halt on all inputs. So I suspect that this formulation does in fact give a more general result.

"It doesn't matter whether that program ever finishes or not"

The program doesn't have to finish, but it has to eventually generate the number to any particular accuracy.

I wrote about this topic a while ago: http://igoro.com/archive/numbers-that-cannot-be-computed/

So, an example of a undescribbible number is infinite sequence of digits generated by a true quantum generator of digits.

Re #27:

Yes, exactly. And per information theory, the vast majority of numbers are, basically, something that could be generated by a true random digit generator.

The way that I actually like to think of it is in terms of compressibility. I know that it's a strange way of approaching it to most folks, which is why I didn't discuss it in the main post. But you can think of a program that generates a representation of a number as a sort of compressed form of the number. And as the standard proofs about compression show, most strings are random and non-compressible. Same holds for numbers: most numbers don't have enough structure to allow us to describe them by anything less than their full infinite representation.

Just wanted to pop in and thank you for this blog Mark. Your writing is clear and engaging and the topics you explain are always thought-provoking. Thanks so much!

Well I guess it gives an whole new meaning to the Friday Random Ten theme.

Of course, this is talking about the set of Reals; that is to say, where every upper-bounded sequence of numbers has a least upper bound. Each real number is actually the limit of some bounded sequence of rationals. Two reals are considered equal if for any arbitrary rational ε, there is always some natural number of terms N past which the two sequences are within ε of each other. Computable real numbers may be represented by the program which recognizes a term in that bounded sequence by halt-accepting. (However, Turing's halting problem means that there are sequences for which there can be no program, no matter what particular Ï you use. On the other hand, Ï can be upgraded with halting oracles if need be... at least, if you're a mathematician.)

I think the Reals requires having the Axiom of the Power Set, but I'm not sure. If so, and if you are willing to take Refutation of the Power set, accepting that there may not be a Power Set for infinite sets (such as the Integers)... there's only one Cardinality of Infinity, and no Reals. At that point, you may take your computing device Ï, the "set" of Ordinals, and denote any "computable" number by the (finite) representation of what level hyper-Ï computing device is required and the (finite) program recognizing the terms of the upper-bounded limit sequence generating the number.

However, most mathematicians like having the Reals instead of just the Countable-Ordinal Computables.

I think it would be more correct to say that the quantity of numbers that we cannot write is not only "most" numbers, but would in fact be an infinite quantity of numbers. So, how many numbers can we write? (1/infinity)?

Re #4:

By creating a physical representation (a line and a point) you have made the number describable. You could count the number of molecules it takes to create the line (with a few assumptions), then count the number of molecules that it takes to go from one end to the point. So not only is the number describable, it's rational.

It's like Feynman's argument with topologists from "Surely You're Joking, Mr. Feynman" about how they could rearrange the pieces of an orange peel, and make it bigger than the sun. Feynman said, "But you said an orange! You can't cut the orange peel any thinner than the atoms."

http://www.physicsforums.com/archive/index.php/t-182942.html

A describable number is a number for which there is some finite representation. An indescribable number is a number for which there is no finite notation.

An "indescribable number", however, does have a form.. it's simply an infinite form, contrary to this statement:

But the fact is, the vast, overwhelming majority of numbers cannot be written down in any form.

Perhaps I am picking nits, but when you say cannot be written in any form, to me that sounds like it has neither a finite nor an infinite representation. That is, it must have no representation at all. I do not believe that any number has no representation in this sense.

Indeed, any number (real or complex) could be realized (or represented if you prefer) as a limit point of a sequence. (#31 alludes to this). To me that is perfectly acceptable from... especially since those numbers you define as describable form a set of measure zero.

Erick: two different kinds of infinity there.

The infinity of the natural numbers is referred to as "Aleph 0", a "countable" infinity. The real numbers have a larger infinity, which the naturals have no bijection (one-to-one and onto) mapping. We can write a countable infinity of numbers, but that still leaves an uncountable infinity of inexpressible Reals left.

Weirdly, the inexpressable reals DO have a one-to-one and onto mapping to the whole of the reals. (Encountering this sort of weirdness for the first time often results in English majors giving up on higher math.)

Paul: Indeed, any number (real or complex) could be realized (or represented if you prefer) as a limit point of a sequence.

The catch is, not every infinite sequence of rational numbers can be finitely represented. And if it can't be finitely represented, you can't write it.

However, if you allow for infinite representations, yes; all real numbers can be expressed by some infinite sequence of digits after the decimal point.

Would it not be easier to just look at the notion of representation without going on about computability. I think that the "computability approach" makes the picture to fuzzy.

If we look at how we can write numbers down we just start by looking at how many different symbols we have at our disposal. We can agree that there is a finite set of symbols but just in case we assume that there are a countable infinite amount of symbols.

Now we piece our symbols together to strings. We can agree that a string can at most have a countably infinite amount of symbols.

So how many numbers can we represent by such a string?

The answer is countable infinite and therefor we can not represent all existing numbers since there are an uncountably infinite amount of real numbers.

So my argument above would show that even if we allow an infinite amount of decimals we still could not represent every number. So there is a more profound result than that there are numbers representable by any FINITE string of symbols.

Paul (34):

That's all well and good, but it's kind-of circular:

Finite representations give us a 'bridge' between the concrete and the abstract - they can be encoded in a computer's memory, or a human mind (modulo some annoying philosophical gymnastics), and then 'operated on'.

On the other hand, an infinite representation of, say, an infinite set isn't any more accessible than just the set itself.

(I suppose one response to all this 'finitude chauvinism' would be to imagine a universe where memories were infinite, and computers/minds could do computations requiring infinitely many steps and return a result. Perhaps time in this universe would look like the "long line" in topology.)

I remember when I first realized that the set of numbers which could be described is countable. It was very disturbing just how big this whole uncountability concept makes things.

I imagined some neo-Lovecraftian story involving a horror from the beyond driving mathematicians mad by pressing an undescribable number in all of it's detail into their minds.

Arne (38): That isn't so surprising. After all, if I count each possible word as a "letter" then I have a countably infinite alphabet.

But whether I classify them as words or letters doesn't change the number of possible sentences.

Moment, please:
As we had the pleasure to learn reals in school by nested
intervals from rationals, can I construct Omega by it ?
And what about Dedekind cuts and decimal expansions ?

I find it a bit furtive to imply that Omega certainly belong to real numbers without mentioning how the reals
in question were constructed.

"We know that they're there; we can prove that they're there."

So we could inductively prove their existence, but not deductively, the limits to computational power could also be indicative of the constraints to notational systems in cognitive situations.

Just use computable math and intuitionistic logic, leave all the other numbers and classical logic to the mathematicians.

No infinity, no problem.

i = 0;
while (1) {
++i;
}

I think this is somewhat addressed by Interval Arithmetic....
http://en.wikipedia.org/wiki/Interval_arithmetic

#13, a program does not have to finish in order to have output. This Perl program never halts, but has plenty of output: print "hello world\n" while 1;

This is the same proof that most numbers are transcendental because there are only as many rational polynomial equations as integers. All computer programs can be reduced to Turing machine programs and there are only as many Turing machine programs as integers. If you count programs that halt or don't halt or blink the little green lights on your Turing machine in a certain pattern, it doesn't matter. At most, you have as many programs as integers.

There are just a whole lot more real numbers than integers.

In fact, there are so many more real numbers than integers that you can do almost all of real number mathematics without the algebraic (non-transcendental) numbers and without the rationals and without the representables.

Now, are unrepresentable numbers interesting? Consider the smallest unrepresentable number. That number is clearly interesting ...

Re #47:

Reminds me of an old UNIX fortune:

Consider the set of all numbers that haven't been considered before ... wait, they're all gone!

What I was trying to get at with my post is that the entire discussion above is that there are numbers that are not finitely representable. It is even given in MarkCC's post:

"A describable number is a number for which there is some finite representation. An indescribable number is a number for which there is no finite notation."

I think it misses the point to talk about numbers that have no finite representation. The interesting numbers in this context are those that have no representation at all, finite or infinite.

Also since I in my proof above allowed for an countable infinite amount of symbols and specified no method of representation we find that most numbers are not describable by decimal expansion. But not only by decimal expansion. They are not describable by any equation or computer program, even IF we allow for the equation / computer program to be infinitely long.

From original post:
"In theory, any number can be represented by a summation series of rational numbers."

It can not both be that this is true and that my argument is correct so I'm going to ask MarkCC to elucidate on this a little.

Arne:

I see the error now.

If your representations include infinitely long strings of digits then in fact the number of possible representations is *uncountably* infinite. This is what Cantor's diagonal argument establishes.

Also, as I said in (38): The whole point about finite representations is that they can be stored and manipulated here in the physical world (by minds and computers). On the other hand, an infinite representation is just as 'remote' from us as the thing it represents.

47: Surely there isn't such a number? There are non-describable numbers in any nontrivial interval of the reals, so the infimum of all non-describables is -infinity (and therefore not a number at all), and that of all positive non-describables is zero (and therefore describable). Which means neither set has a minimum... neither does any subset of the non-describables that you can finitely describe, because if the infimum (or supremum, or essential infimum/supremum, or just about anything else you can ask for) of such a set is a real number, it's obviously describable.

What is a notation system?

I take it that the English language doesn't count? If it did, it would seem like you can describe at least one indescribable number as follows: "The first positive indescribable number."

Though I just realized that description might not uniquely describe any number if, given one indescribable number, there's always another one between it and zero.

And no similar description would pick out an indescribable number uniquely if, given any pair D and I where D is describable and I is indescribable, there is a B which is indescribable and which is between D and I.

Which seems plausible.

Never mind then.

Kris:

Replace "smallest indescribable real number" with "smallest indescribable ordinal" and you have your paradox.

Its probably already been pointed out (I didn't read all the comments thus far) that this concept was the focus of a paper written by Alan Turing in 1936. In the process of inventing the computer, he already realized the shortcomings of computers in that they can only deal in "computable" reals. He recognized that even irrational numbers, although having infinitely many digits, they can possibly have a finite representation, and are thus computable. Unfortunately it can be shown via Borel measures that when randomly selecting a real number from a unit measure it is infinitely improbable that the selected number would be a "computable" real. There is an excellent lecture by Gregory Chaitin on these very ideas here:

http://www.youtube.com/view_play_list?p=6A6833CBFA87B5C8

Great blog, Mark. Keep it up.

Neil - what you described requires the Axiom of Choice, if I'm not mistaken.

You state, in your definition of an 'indescribable' number, that 'given the first K numbers in that series, there is no algorithm that can tell you the value of the K+1th rational. '

You can write a very simple algorithm which, given the first K values in the decimal expansion, writes down all 10 possible K+1 values. How this basic counter-example could have been overlooked is baffling.

The very fact that a decimal expansion exists means that the number is computable, so your argument makes no sense.

You need to include in your definition that the program has to halt. If it acts like you say, that 'It doesn't matter whether that program ever finishes or not', then the program I described above satisfies your conditions.

Re #66,67:

The "program" you describe doesn't output a specific number. The definition of a describable number (or at least, the definition that I'm using for this post) is that there exists a program which generates that number, and only that number - that is, that there is a program which is a description of the number.

You can write a program that generates all of the finite rational sequences - but it will never generate an infinite one. And there's no program that uniquely specifies or describes an indescribable number.

Or, to put it another way: almost all numbers are boring.

I suspect a clearer definition is one in terms of limits. The definition of a computable number x is one for which you can produce an function of N and some N such that for any ε, f(N)-x < ε. With an indescribable number there is no such f. There may be particular ε that you can find an f and an N, but no general case.

Something I wonder in relation to the genetic algorithm comment is whether you can produce a program that will produce a correct limit for a given ε with some probability p that is better than guessing. i.e. if you have a value for ε, can you produce a value for 0.1ε with p > 0.1.

Interestingly, there is a famous paradox lurking in the vicinity of the point in this post - take the sentence "The smallest positive integer not definable in under eleven words." Well, there is such an integer, isn't it? But I just described it using less than eleven words.

Many people, on encountering Berry's paradox, think it's kinda silly (just as they do with the liar which trades on the same semantic knot). What's utterly awesome, however, is the way Boolos used this one to give the until now by far shortest proof of Gödel's incompleteness. The idea behind the proof is to hold a proposition that holds of x if x = n for some natural number n to be a definition for n, and then show that the set {(n, k): n has a definition that is k symbols long} is representable with Gödel numbers. "m is the first number not definable in less than k symbols" can thus be formalized and shown to be a definition.

Ok. I'm not sure this is related too closely to the discussion at hand (but it is related to the title of the post), but wanted to share it anyway.

TSK: As we had the pleasure to learn reals in school by nested intervals from rationals, can I construct Omega by it ? And what about Dedekind cuts and decimal expansions ?

Yes, you can construct Omega that way... once you figure out how to construct the set of all Turing Machine programs that halt. Which, finitely, you can only do by axiom. Which acts as an Oracle, acting to increase the power of your Ï to a hyper-Ï, and giving you the possibility of a hyper-Omega.

Repeat ad infinitum et nauseam.

Arne: It can not both be that this is true and that my argument is correct

Your error is in presuming that all sequences of rational numbers have a finite representation.

Stephen Jones: The definition of a computable number x is one for which you can produce an function of N and some N such that for any ε, f(N)-x

...where ε is a rational number; and |f(N)-x|, if you want computables and not merely computable Reals. The computables spill out into the Complex plane, too.

"All sorts of things that we count on as properties of real numbers wouldn't work if the indescribable numbers weren't there. But they're totally inaccessible." Sometimes it's good to remember what Cantor himself believed: that numbers have an "intrasubjective and immanent reality." Perhaps there is a reason why they chose the following words when they put up a plaque in Halle commemorating Cantor's innermost conviction that "the essence of mathematics lies in its freedom." - "No infinity, no problem?" No infinity, no cry? Cantor didn't mind shedding a few tears over the beauty of the inaccessible. These tears can be thought of as dense and indescribable as the reals.

Whether the program halts or not is not an issue. The program does not have to halt. A program that computes all the digits of pi or the square root of two never halts. There is no last digit in either case.

The problem is that there are not enough programs. A program is an integer. There are only so many integers. There are many, many more real numbers. Programs always produce the same output each time they run. That means that there are lots of numbers out there that you cannot write a program to compute.

This is just like our host's discussion of compression algorithms. There are more long strings than short strings, so any algorithm that maps lots of long strings into shorter strings will actually have to map lots of short strings into longer strings. It's just counting.

If we want to get around this, we have to define a mechanism for programming in which the programs are real numbers, not integers.

It's possible to write descriptions that always halt.

For example, say that a function f of one variable describes a real number y iff, for any x > 0, f(x) terminates and |f(x)-y| < x

If those numbers are 'undescribable' and 'inaccessible', what are they usuful for? Can we define the set of all describable reals and prove the essential theorems about reals for that set?

Re #66:

Who said that things need to be useful?

Seriously, the basic definitions that we use for real numbers
necessarily imply that those numbers exist. You lose an awful lot of basic stuff when you try to create a reduced set of real numbers. People have done work on computable numbers, which are close to the definition of describable numbers, and you *can* do it, but it's a lot of work, and it's clear that you're really constructing a subset of the numbers. The fact that they're conceptually there is pretty
much unavoidable.

You can drop the irrationals entirely, and wind up with the rational numbers. They work pretty nicely for lots of things. But algebra breaks: a polynomial of degree N no longer has N roots, because there is no rational number that can solve many of them. In a universe of rational numbers, where does Y=2-X2 cross the X axis?

The original critique of Dembski said: "Unfortunately, most real numbers are undescribable. There is no notation that accurately represents them. The numbers that we can represent in any notation are a miniscule subset of the set of all real numbers. In fact, you can prove this using NFL."

Could you clarify how this is proved using the NFL theorem?

There is a related thread now at the n-Category Cafe blog ("boundless" is in its title, something like "Bounding the Boundless") about the philosophical history of Infinity, with special attention paid to Giordano Bruno, Isaac Newton, Isaac Barrow, and Isaac Asimov.

It might be fun for some readers here to read that also, and comment there as well as here.

n-Category Cafe has blogmasters expert in Mathematical Physics, Philosophy of Mathematics, and Computation Theory.

JC wrote:

> What if the program describing the number *isnt* finite, but can be described itself by a finite program? Like a genetic algorithm, for example.

This doesn't work. Where are the random numbers coming from? The Turing Machine is deterministic, remember. There's just the symbols on the tape, and a fixed set of rules. If the random numbers aren't included in the program, then it can't do anything; if they're included then you run into the same problem as for other programs.

What???

:)

"Re #3:

That's not an escape. It comes back to basic computation theory: if you could write a program that generates a program that does X, you can write a program that does X.

If you could write a program that could generate an infinitely long program that generated a number, you could bypass the middle step and just write a program that generated the number. "
It is at least not so simple, because math theorems You mention about are regards first order logic. So if You where able to made some validity of second ( or higher) order logic programming, things may be quite different. The most iportant thing in Your post is conception of computality, which is only just that: conception with stright and tight definition.

In a finite universe, are there undescribable integers?

Kevin @ 73 asks:
"In a finite universe, are there undescribable integers?"

Rather than quibble about whether "finite" means space, or time, or both, and whether "undescribable" applies to integers exactly as it does to reals, then YES.

If there are N possible states of the finite universe, then there are at most N descriptions of integers that can occur in any given state of the universe. Hence there are no more than N describable integers. So if I have a set of N+1 distinct integers, including each of the N describable integers, then that set must contain an undescribable integer.

That is motivational, and not crisp enough to be axiomatical, but you see why I say "YES!"

And you should also see why it gets back to "compressibility" as Marc CC has explained it.

In your proof, you state "The number of programs for any effective computing device is countably infinite...." Remembering the roots of programming in analogue computers, the voltages, resistors, potentiometers, etc. could take arbitrary values in the set of Reals. As such, I would argue that *some* computing devices have an uncountably infinite amount of possible programs.

I took a random walk through the blogosphere and found a site with a nest of posts regarding indescribable numbers, Berry's Paradox, incomputability, Turing machines and "compressibility". And I, having small mathematical ability but some acquaintance with Douglas Hofstadter, I took the "road" (read explanation of the improbable) less intuitively obvious.
Great site and comments.

plain and simple kids, if you want indescribable numbers, look for numbers which no algorithm could generate. pi can be described by geometry, hence its identity is known and can be clearly written in code. indescribable numbers can be irrational and/or infinite and rely on currently non-existing logical framework.

an interesting question: is it possible to prove all the limits of our algorithms and hence locate where all the indescribable number definitions/generators lie?

Partial randomness and dimension of recursively enumerable reals
Authors: Kohtaro Tadaki
(Submitted on 15 Jun 2009)
http://arxiv.org/abs/0906.2812

#5: pi is easy to describe. It is, as you sure know, the ratio of radius to the circumference of a circle. A perfectly valid description. MCC never said that it has to be described in the decimal system, in fact he stated the opposite.

Can you write the these numbers or represent these numbers in Mayan?

54 or 1954?

If I take a stick that is 28 inches long and I use my dividers/compass to divide it into 6 equal sections, I will be successful. I can physically divide a 28 inch long rod into 6 equal sections. But I can't divide 28 by 6 on paper. Math seems to need some improvement. Our base 10 system does not seem to work. We need some other way to talk about numbers.

But I can't divide 28 by 6 on paper.

sure you can. 28/6 = 14/3 exactly; there's nothing wrong or odd about fractions. use a smart enough calculator and it'll throw that expression into exact fractional format for you, no questions asked.

Our base 10 system does not seem to work

no worse than any other positional-value number system. one key insight is that number bases really aren't as fundamentally important as we sometimes think they are. in many ways, strings of digits with an optional decimal point is just a notational convention; it's not something that defines what numbers really are.

Indescribable numbers don't exist unless you can give an example.

@83

There are some mathematicians who work with 'constructive' mathematics whou wouold agree with you. They work with the intuitionistic variety of logic in which the law of the excluded middle ( A or Not A ) does not apply.

However most mathematicians work with 'classical' logic in which, to prove the existence of something, it is sufficient to show that a contradiction would result if it did not exist. By definition, no example of an indescribable number can be given - so you cannot constructively prove they exist, but if they did not exist, then you can prove a contradiction with the definition of the real numbers (as a complete, archimedean, ordered field).

I believe this is a direct consequence of the Borel-Cantelli lemmas. In that if x is an irrational, and p/q is rational in lowest terms, then |x - p/q|< 1/q^2, but if you want to approximate it better, then the set of p/q such that |x-p/q|<1/q^(2+e) is a null set for any e>0.

jman said:

> plain and simple kids, if you want indescribable numbers, look for numbers which no algorithm could generate.

It's certainly not so plain and simple, after all you got it wrong. In fact, Chaitin's main claim to fame is a number named after him that is describable but that no algorithm could generate.

This argument really says that Turing Machines cannot write down all numbers.

The jury is still out as to whether or not humans have "free will" and I think that, if we do, we don't know if it would be Turing Equivalent.

So it's supposedly conceivable that a human might be able write down all possible numbers -- or am I missing something?

@87:

You're missing something.

What the "undescribable" thing really means is that no notation can possibly represent the vast majority of numbers. And since any combination of a finite number of notations is still a notation, then no finite combination of notations can possibly represent the vast majority of numbers.

If you start allowing an infinite number of notations, then things start getting weird. But still, you wind up with even any combination of a countably infinite number of notations can't represent most numbers.

So you end up with the fact that to represent all numbers, you need an uncountably infinite number of notations. And if you do that, you wind up right back where you started: now you have undescribable notations.

I have a problem with the statement: "The number of programs for any effective computing device is countably infinite..."

This is true only if all programs are finite. Otherwise, it's trivially not true. Let Y be the set of all programs. Let X be the set of all finite subroutines (a library of all finite subroutines if you like). This set is at least countably infinite and also this set is a subset of all programs Y, since some programs consist of single finite subroutine.

But, the power set of P(X) (i.e. set of all subsets of X) is also subset of Y, for every combination of subroutines from X forms a (possibly infinite) program. But the power set P(X) in uncountably infinite if X is countably infinite (which it is). Since we have shown that P(X) is subset of Y, so Y must be uncountably infinite.

Mark,

You are making this more confusing than it needs to be. You defined your representations to be finite. You then say one way to approach this is to consider programs generating these representations. But if the representations are finite, this adds nothing. You can simply write programs that print out the representation. Talking about programs adds nothing. Programs only become interesting if you consider infinite representations (like decimals) because then you can generate some of those with finite programs. Every finite string is computable so talking about computers simply adds a level of indirection.

My main point is that computability is not the same as describability but you're giving the impression it is. (Consider, eg. Chaitin's constant.) In fact, I think you ought to have made this distinction clearer.

#2: To put it another way:

Natural numbers (countably infinite) â programs that run â programs that terminate

Assuming that some of the outputs of the last set of programs are unique descriptions of numbers, that can't describe all numbers, since a subset of a countably infinite set can't cover an uncountably infinite set. That still holds if each output is a description of a finite number of numbers, since the union of a finite number of countably infinite sets is itself countably infinite.

What if a sequence of symbols could denote an infinite set of numbers, though? Would the above proof still hold? Does that depend on whether the set of possible encodings is countably or uncountably infinite?

Actually, never mind that last bit. The set of possible encodings must be countable, since you can just take the (finite) set of characters currently used to encode meaning and start enumerating, a subset of those strings will describe all possible encodings.

I'm pretty sure the cross product of two countably infinite sets is still countably infinite, so the proof above still holds even given that one output string can represent more than one number (possibly an infinite number of numbers).

I find the idea that most numbers are undescribable interesting. I was looking forward to reading about how you'd quantify. Wanna write a post on that?

this is one of my favorite topics related to numbers. It makes me think that the "real" numbers are oddly misnamed.
I know that numbers aren't strictly "real", but still, if a number can never be used, can never even be talked about specifically, then what the hell is this number. how can this number even be said to BE something!