Can someone give me a simple explanation of what a non-computable number is?

I think wikipedia explained it well:
In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. Equivalent definitions can be given using μ-recursive functions, Turing machines or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes.

So a non-computable number is any number (it’s an infinite set) that doesn’t meet that definition.

” μ-recursive functions, Turing machines or λ-calculus as the formal representation of algorithms.”

Huh? I don’t think Wikipedia explained it at all well. Basically, the definition above describes in not-very-clear technical terms what a computable number is, and then, in the last sentence says “Not that.” Hence my question.

Okay, let me try again—this is a very advanced aspect of number theory, so it’s not going to be terribly easy. They key, is of course, that we need to develop a definition of a “computable number”, and anything that’s not that is non-computable.

The key up there is the “numbers that can be computed to within any desired precision by a finite, terminating algorithm.” So, if you can write an algorithm for a turing machine, a Mu-recursive function, or Lambda calculus function, you’ve got a computable number.

Basically, you can’t simplify it any more. Take @grumpyfish ‘s advice and focus on ”[real] numbers that can be computed to within any desired precision by a finite, terminating algorithm”. Non-computable reals are what’s “left over” when you subtract those from the reals. Though the “left overs” in this case have the same cardinality as the reals given that computable numbers have the same cardinality as the natural numbers. In other words, virtually every real number is non-computable.

You can think of a computable number as any number that can be calculated to any desired degree of accuracy after a finite number of steps using a computer program. Computable numbers include all rational and algebraic numbers as well as some transcendentals like pi and e.

A way of thinking about it in informal terms is that a computable number is one that can be described in a finite number of words. It is somewhat mind blowing to realize, as @hiphiphopflipflapflop points out, that nearly all numbers are non-computable, meaning that nearly all numbers are indescribable. If there were a way of choosing a number completely at random, there would be less chance of knowing what you had than of finding intelligent life at a random location in the universe, though maybe not in the multiverse.

So then a prime number like, say, 5, would not be “computable”?

0 0 0

Triple zero does not compute, according to The Internal Revenue Service.

@Zuma Finite algorithm: Add 1 to itself four times and stop. :) 5 is computable. Every natural number is computable. Every rational number is computable. Every algebraic number is computable.

A non-computable number is essentially random. An informal way to think about them is that each one has infinite information content that cannot be compressed into a finite expression.

How to generate a non-computable number.

Decimal expansion goes as:
0. (a1) (a2) (a3) ...

Where a’s are given by successive rolls of a ten-sided die or lottery draws with balls numbered 0 through 9. Now do it “infinitely-many times” to get the full expansion.

The chance this process has of producing a computable number is exactly zero.

@Zuma OK, I think I see where I tripped you up. That’s why I made that aside as a whisper. Given the whole set of real numbers, all the usual numbers that are familiar to us are freaks!

@hiphiphopflipflapflop I also assume something like calculating pi through sucessive approximation, e.g. is non-computable because of the sigma -> infinity?

@grumpyfish Pi is computable as you can get as close as you want with a single program.

With a random number, you can fit a program to it that will give you some set number of digits of the expansion, but go further than that, it craps out and you need to make a new program, and so on and so forth.

@hiphiphopflipflapflop Ah! That’s the “within any desired precision” part!

@hiphiphopflipflapflop Mkay, I think I got it. This sounds like what Jorge Borges was describing in The Garden of Forking Paths, where he describes the Library of Bable:

“The impious maintain that nonsense is normal in the Library and that the reasonable (and even humble and pure coherence) is an almost miraculous exception. They speak (I know) of the “feverish Library whose chance volumes are constantly in danger of changing into others and affirm, negate and confuse everything like a delirious divinity.’’ These words, which not only denounce the disorder but exemplify it as well, notoriously prove their authors’ abominable taste and desperate ignorance. In truth, the Library includes all verbal structures, all variations permitted by the twenty-five orthographical symbols, but not a single example of absolute nonsense. It is useless to observe that the best volume of the many hexagons under my administration is entitled The Combed Thunderclap and another The Plaster Cramp and another Axaxaxas mlö. These phrases, at first glance incoherent, can no doubt be justified in a cryptographical or allegorical manner; such a justification is verbal and, ex hypothesi, already figures in the Library. I cannot combine some characters

“dhcmrlchtdj”

which the divine Library has not foreseen and which in one of its secret tongues do not contain a terrible meaning. No one can articulate a syllable which is not filled with tenderness and fear, which is not, in one of these languages, the powerful name of a god. To speak is to fall into tautology. This wordy and useless epistle already exists in one of the thirty volumes of the five shelves of one of the innumerable hexagons—and its refutation as well. (An n number of possible languages use the same vocabulary; in some of them, the symbol library allows the correct definition a ubiquitous and lasting system of hexagonal galleries, but library is bread or pyramid or anything else, and these seven words which define it have another value. You who read me, are You sure of understanding my language?)”

If you can imagine a word of infinite length that, obviously, can not exist in any finite library, and additionally whose construction can not be specified within the library then you have an idea of a non-computable number

Okay, I think I get it now. It is more like the library itself—which is a metaphor for a landscape in the sense that physicists and biologists use the term. One part of it cannot be used to deduce the whole. It can be searched for and found, decimal place by decimal place, but only in a brute force kind of way; say, by experimentally interrogating some aspect of nature. In other words, no algorithm can reveal or produce it. Thus, to the extent some cosmological parameter depends on one of these numbers, that aspect of the universe can not become known to us through mathematical deduction alone.

Just a few points I feel necessary to interject at this stage:

My understanding is that the string theory landscape is large, but finite (based on a rather arbitrary limit on the number of holes allowed in the compactified Calabi-Yau manifold as well as the number of flux lines that thread through each hole). Lifting those limits would leave you with an infinite set, but still of the same order of the natural and rational numbers.

Mathematicians generally consider “Dedekind cuts” or Cauchy sequences as valid means of “constructing” the set of real numbers from the set of rational numbers. There is in some sense a finite instruction set (though containing many infinite operations) that gives you the whole set of reals, fine and dandy. When it comes to picking out individual numbers, there is a problem as nearly all of them on their own are non-definable as well as non-computable. Omega is an example of a non-computable number that happens to be definable.

I was not aware that there were numbers that are definable but not computable. Is there a proof that omega is greater than 0?