Talk:Computable number

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Foundations, logic, and set theory

Contents

[edit] comment by user:Cwitty

I removed the following incorrect definition from the main "computable number" page. The set of numbers described by this definition is not even closed under addition (plus, you would get a different set of numbers in different bases). -- Cwitty

A real number is called computable if its digit sequence can be produced by some algorithm. The algorithm takes a natural number n as input and produces the n-th digit of the real number's decimal expansion as output.

Thanks for the catch! I thought this was the original definition given by Turing, but apparently not... AxelBoldt 17:21, 23 Feb 2004 (UTC)
AxelBoldt has pointed out (on my talk page) that the definition I removed above is similar to Turing's original definition (although, to be nitpicky, Turing used binary rather than decimal). I apologize for calling it "incorrect" above. Cwitty 02:40, 4 Mar 2004 (UTC)

From the article:

"and arguably this field contains all the numbers we ever need in practice"

This, of course, depends on physics. Does anyone know anything about the current state of research in this area (eg Pour-El and Richards + ensuing work)? It would be great to have a seperate article on this topic. -- Pde

[edit] Clarify informal def?

the computable numbers, also known as the recursive numbers, are the subset of the real numbers consisting of the numbers which can be computed by a finite, terminating algorithm

This definition could be taken to apply to the c.e. reals as well, depending on what it means to "compute" a real number. Of course the definition is made precise later in the article, but it would be nice if it were a little clearer here. I admit no wording jumps to mind--suggestions solicited. --Trovatore 19:39, 19 July 2005 (UTC)

[edit] Countability

Instead of repeating the well-known proof for the uncountability of the reals inside ZFC the article should explain why the set of computable numbers is countable inside ZFC, i.e., how to formalize the notion of an algorithm and how to construct a bijection with N.--80.136.170.149 11:53, 9 August 2005 (UTC)

The phrase "countable inside ZFC" is a category error (syntax/semantics confusion). Probably you mean "...why ZFC proves that the set of computable numbers is countable". --Trovatore 14:43, 9 August 2005 (UTC)
I'm not an expert, but I've heard rumours that there are countable models of ZFC, so the reals inside this model are "externally" countable, but of course not "internally". So my question is whether the countability proof sketched in the introduction really shows "internal" countability. As an analogous case, consider the real numbers which can be described uniquely by some "ZFC" formula. (This is probably a category error, again.) The collection of all these is obviously "externally" countable since the collection of all formulas is countable, but it is not even clear to me how this set could be described formally, let alone how its countability could be proved.
Or is all of this nonsense?--80.136.170.149 20:45, 9 August 2005 (UTC)
No, it's not nonsense. For countable models of ZFC, see Skolem's paradox. For real numbers describable by some ZFC formula are the definable numbers. But the countablility proofs can be "internal", because ZFC is strong enough to express "formula of ZFC" -- in fact, basic arithmetic is strong enough to express "formula of basic arithmetic", which is of course Goedel's incompleteness theorem 192.75.48.150 19:04, 10 August 2005 (UTC)
I think I understand now. Thanks a lot.--80.136.136.219 22:14, 10 August 2005 (UTC)
One thing I still don't understand (and which is not sufficiently clear in definable number) is the following: So one can prove the existence of an enumeration of the set of definable numbers, say by lexicographically ordering the corresponding formulas. Why is it impossible to use the Cantor diagonal procedure applied to this enumeration to determine another definable number?--80.136.136.219 23:41, 10 August 2005 (UTC)
It is possible--but the new number won't be definable in the same sense. The set of all reals definable by a first-order formula of the language of set theory (please! not "formula of ZFC") is itself not definable by a first-order formula of the language of set theory. See my remarks in the talk page Talk:Definable number; I had to do some major work on that page. --Trovatore 01:38, 11 August 2005 (UTC)
So how can you express its countability in the language of set theory (let alone prove it using ZFC)?--80.136.140.96 14:44, 11 August 2005 (UTC)
Strictly speaking, you can't. Its countability is clear informally, and can be proved in some stronger theory, say Kelley-Morse (so-called "second-order ZFC"). --Trovatore 16:54, 11 August 2005 (UTC)
In this context, it may help to think of Wikipedia looking at ZFC, and ZFC looking at what I shall call q(ZFC). ZFC has no notion of "me", and when it looks at q(ZFC) it sees an abstract set of rules for manipulating symbols; Wikipedia sees that q(ZFC) is in fact equivalent to ZFC.
Consider what I shall call r(X), the set of all formulas in a suitable formal system X which define a real number (in the sense we've been talking about). It is provable, in ZFC, that r(q(ZFC)) is countable. And the diagonal argument works in ZFC to obtain a new number, but since the argument is in ZFC and not q(ZFC), the new number will be a member of r(ZFC), but not of r(q(ZFC)).
But Wikipedia sees that ZFC and q(ZFC) are equivalent, so Wikipedia asks why the diagonal argument doesn't work in q(ZFC)? It does, but q(ZFC) doesn't know about "me" either, it only sees q(q(ZFC)), which to it is just an abstract set of rules. It is provable in q(ZFC) that r(q(q(ZFC))) is countable, and the diagonal argument in q(ZFC) produces a new number which is a member of r(q(ZFC)) but not r(q(q(ZFC))). (And in fact ZFC sees that q(ZFC) and q(q(ZFC)) are equivalent. Perhaps ZFC even laughs at the foolishness of q(ZFC).)
That's "definable numbers" though. For computable numbers, to even start the diagonal argument, you have to order the algorithms, and there is no algorithm which can do that, so the result is not a computable number. Do you think either of these two pages need further explanation? 192.75.48.150 20:56, 11 August 2005 (UTC)
Gotta tell ya, 192, not meaning to be unkind, I don't think you've exactly cleared everything up here. If you want to discuss such matters in detail, I'd encourage you to register, rather than editing from an IP address, so this sort of thing can be discussed on your talk page. --Trovatore 20:57, 12 August 2005 (UTC)
Uh oh, now I've done it :-) Okay, here I am. Honestly, I was asking the other guy, because he was confused, and I wasn't sure why. I think you already understand everything better than I do. Fool 02:43, 13 August 2005 (UTC)

[edit] Can computable numbers be used instead of the reals?

"However, one obvious and important point of failure lies in measure theory. A fundamental property of the standard outer measure on the reals is that the measure of any countable subset of reals is zero. This property cannot be kept in the computable reals since it would cause the measure of any subset to be zero, rendering measure theory trivial and useless.

This also causes standard probability theory to fail, since abstract probability theory is founded on measure theory. For example, the above property of the outer measure allows us to deduce that the probability that a infinite series of coin tosses degenerates to all tails is 0, in accordance with our intuitions. Without standard measure theory, there is no obvious way to obtain this result.

Intuitively it is hard to see how probability might be defined without resorting to uncomputable numbers. The result of an infinite series of coin tosses will normally contain an "infinite amount of information", so an uncountable set is required to express the set of all such series. Indeed our intuition tells us that the probability that such a series can be expressed by a Turing machine should be 0, since an occurrence does not seem truly "random" if it always falls into a predictable pattern."

Constructively, even if given a set containing a countable set, and contained in a countable set, it does not follow that the set is itself countable, does it? And an infinite series of coin tosses would be rejected altogether ("actual" infinity), no? Instead, the probability that a finite series of coin tosses of arbitrary length ("potential" infinity) would come up all tails approaches zero as the length of the series increases. Fool 18:37, 9 August 2005 (UTC)
The computable numbers are countable, but they are not computably countable, meaning that there exists no conputable bijective function Z: T, where T is the set of all computable numbers. Using this definition of computable countability instead of Cantor's definition of countability, it is possible to define the Lebesgue measure such that the length of an interval [a,b] in T is b-a, the measure of any product of n intervals in T^n is equal to the product of the lengths of the intervals, and the measure of any computably countable set (such as the integers or the rational numbers) is 0. Measure theory, then, is not 'trivial' or 'useless', and probability theory does not fail.

[edit] removed remark

I've removed the following remark:

(Interestingly, we can define this diagonal number in a finite amount of English, such as this paragraph - though it is uncomputable! This is perhaps due to the assumption that we can 'imagine ordering the computable numbers' for the Cantor proof, while this is not algorithmically possible in practice.)

It's not about "imagining" such an ordering; all this shows is that we can define more than we can compute. As for what's possible in practice, that has nothing to do with whether an algorithm exists. There are things we can't do in practice, that are algorithmically very simple: For example, counting to a googol. --Trovatore 07:53, 5 December 2005 (UTC)


[edit] “Computable real number”, as defectively defined in the main article, is an interval or a variable

The 2 equivalent definitions of a “computable real number” presented in the main article very clearly identifies an _interval_ or a _variable_ and not a _point _ or a _real number_ (which is a constant). All real numbers are definable, countable, computable, and can be well-ordered. Starting with any known irrational number (which is a constant --- hence, definable and computable by having identifiable digits for all natural number place value positions), say square root of 2 or pi or e, then any real number can be defined, counted, computed, and well-ordered by simply delineating how its, say, decimal or binary system expansion digits (there are only a finite number of these digits --- 10 for decimal system and 2 for binary system) differ digit-for-digit (with their respective expansion point aligned, starting from the leftmost digit going to the right with 0 for blank) with that of a given irrational number constant.

Indeed, the “concept” of “computable real number” merely redounds (with inherent self-contradiction) to “rational number” while that of “noncomputable real number” to “irrational numbers” variable or interval. The “concept” of “undefinable real number” is nonsensical because it is truly self-contradictory --- it simply blurs the distinction between the definition of a _constant_ (or _point_) and that of a _variable_ (or _interval_) “real numbers”.
The claim that Cantor’s diagonal argument does not work to “establish” the “uncountability” of the “computable real numbers” which are _intervals_ and the anti-diagonal “real number” which is a _point_ (it is a “real number” merely because of the prefixed fractional place-value-positional-numeral-system representation expansion point and the claim that it lies between 0 and 1) is the same reasoning as applied to the row-listing of rational numbers and its anti-diagonal irrational number variable (or arbitrary constant which is not a true constant!).
Please read my Wikipedia discussion notes on “Cantor’s diagonal argument”, “Cantor’s theorem”, “Cantor’s first uncountability proof”, “Ackermann’s function”, “Boolean satisfiability problem”, “Entscheidungsproblem”, and “Definable number”. (BenCawaling@Yahoo.com [13 December 2005])BenCawaling 06:22, 28 March 2006 (UTC)


The definition specifies a descending sequence of intervals, not a single interval. -Dan 16:09, 13 December 2005 (UTC)
So it is with the definition of an irrational number as a convergent sequence of rational numbers. Georg Cantor had to posit ordinal numbers, in particular w (omega), to get to the irrational numbers. There is a huge conceptual leap from _descending intervals_ to _point_ and it is this vagueness in definitions (why can it not just "converge" to another "interval"?) that causes self-contradictions. What is your objection to my assertion about the "definability, countability, computability and well-ordering of all real numbers" in the first sentence above? [BenCawaling@Yahoo.com (14 Dec 05)]
I'm sorry, I haven't really gotten around to reading all your notes. I have no objection to computability of all real numbers in particular, and there's a perfectly respectable way of doing that. I started talking about it Constructivism (mathematics), but I haven't got around to that either. -Dan 17:56, 16 December 2005 (UTC)
Well, then, it's about time you did --- constructivism makes sense. We need to have more people discussing _intelligently_ this stuff. BenCawaling@Yahoo.com [19 Dec 2005]

[edit] Uncomputables as a consequence of ZF

The last passage of the proof is:

Some members of P(N) are "infinite in size", so cannot be captured by a finite machine. It is these members that form the uncomputables.

But, for example, the set of all even numbers is "infinite in size", is a member of P(N) and yet can be captured by a finite machine, so I think this statement should be revised or better explained.

I think the "proof" really ought to be clarified on this point. Is the reader supposed to interpret the "infinite in size" predicate in some way other than cardinality? For example, shall we call a set of integers "infinite in size" if it encodes all non-halting Turing machines? (For all I know, this may be enough to establish the claim, but I am not a logician.)
I added a parenthetical comment to the text that the "infinite size" members of P(N) map to reals composed of non-repeating binary fractions. My hope is that this is a little clearer and does not lead to the misconception that all infinite subsets of N are uncomputable (such as the subset of all evens, as you said). It's still not completely correct (because many computable reals have non-repeating fractions, such as \sqrt{2}), but it's closer to correct.
Perhaps "infinite in size" is the misleading part here. After all, most of the subsets of N are infinite (only a countable number of them are finite).
-- Loadmaster 22:22, 5 June 2006 (UTC)
Yes, it's closer to correct, but as you say, still a way out. I'm actually going to cut the entire section. Here is the cut text:
An uncomputable number can be intuitively viewed as a number which is "infinite in size", or containing an "infinite amount of information". In other words, it is an element of the set of reals which cannot be expressed (i.e. distinguished from all other elements of the set) using a finite number of symbols. The uncomputable numbers arise as a consequence of the Zermelo-Fraenkel (ZF) axioms as follows:
ZF assumes the existence of the natural numbers, N, and the existence of the power set of every set.
So the power set of the naturals exists, P(N).
We can encode the reals, R, in binary notation, mapping the n-th digit to the presence or absence of n from a member r of P(N). So there is a mapping between P(N) and R.
Some members of P(N) are "infinite in size" (which map to the reals consisting of an infinite sequence of non-repeating binary digits), so cannot be captured by a finite machine. It is these members that form the uncomputables.
We have a statement further up:
There are however many real numbers which are not computable: the set of all computable numbers is countable (because the set of algorithms is) while the set of real numbers is not (see Cantor's diagonal argument).
I think that will do unless and until we get our story straight. -Dan 13:46, 6 June 2006 (UTC)

[edit] Is this a typo?

In the last section is written: "no uncomputable element can be expressed using a finite number of symbols". Isn't this wrong? What about Ω? Is 'expressed' a bad choice of words, or is this plain wrong? —The preceding unsigned comment was added by Etatoby (talk • contribs) 21:53, 2 April 2006 (UTC)

I would lean to "just plain wrong". I would also say the following line
In some sense the computable numbers include all numbers which are individually "within our grasp".
is wrong, though of course it depends on what sense "some sense" is.
By the way, by Ω I take it you're talking about Chaitin's constant. It should maybe be pointed out that many people seem to think Chaitin was the first person to give a precise characterization of an uncomputable real. That is not at all correct. The set of all Gödel numbers of Turing machines that halt is denoted 0', and the fact that it could be coded by a real and that it's not computable long predates Chaitin.
In general, Chaitin's math is right, his interpretations are somewhat arguable, and claims that he originated some revolutionary change are almost always overblown. It is possible to be, at the same time, very good and very overrated. --Trovatore 22:47, 2 April 2006 (UTC)
While I'm in a huffing mood, I huffed that too. -Dan 14:09, 6 June 2006 (UTC)

[edit] Formal definitions

I'm not sure about that computable Dedekind cut definition. I actually think it is in the same boat as the "digit sequence" definition: equivalent, but not computably equivalent. Also, I think the error-bound definition should be stated with a rational error bound. How do you give a real error bound to an algorithm? -Dan 14:09, 6 June 2006 (UTC)

I agree. "Dedekind-cut computable" numbers are computable according to the other definitions, but the converse is not necessarily true. Take for instance the limit of the sequence (an)n where an = 1/n if there is no counterexample < n to the Goldbach conjecture, and otherwise 1/c where c is the first such counterexample. This limit is computable also in the sense of constructive or intuitionistic real numbers, but you must be a classical Platonist to believe that there is necessarily a function D that does the trick. This kind of spoils the beuaty of the idea of "computable number". The |r-a| ≤ ε definition should be turned into something more Cauchy-like; as presented it requires a belief in the existence of real numbers separate from their computability -- which, again, spoils the idea. Basically all you need is a computable function f from the positive rationals to the rationals such that |f(x)–f(y)| ≤ |x-y|. --LambiamTalk 21:42, 17 June 2006 (UTC)

[edit] Edit of 2006-7-14

  • I removed the following sentence. It isn't clear what the word require is supposed to mean. I'm sure the topos theorists don't agree...
In contrast, the reals require the more powerful axioms of Zermelo-Fraenkel set theory.
  • I fixed the tone to make it encyclopdic, and removed the first person pronouns.
  • Added the Cachy sequence characterization of computable reals.
  • I clarified why the computable reals are not robust enough for elementary calculus
  • I added a reference and clarified to relation to constructive mathematics
  • Cleaned up the reference to Chaitin numbers.

CMummert 12:24, 14 July 2006 (UTC)

Good work. Paul August ☎ 15:30, 14 July 2006 (UTC)

[edit] Different definitions

There is no algorithm which takes as input the description of a Turing machine which produces ε approximations for the computable number a, and produces as output a Turing machine which enumerates the digits of a in the sense of Turing's definition.

While I believe this should not be hard to prove, this should probably need a citation (the same holds for other assertions inside the article). David.Monniaux 21:19, 14 February 2007 (UTC)

It's almost trivial to prove and was first established (in different language) by Turing himself in his published correction to the paper in the references section. Suppose that there was such an algorithm. Then I can force the algorithm to be incorrect as follows. I start enumerating the sequence 1.0, 1.00, 1.000 of approximations to a real number, with the nth approximation guaranteed to be within 10^{-n} of the true value. I feed this sequence to the purported algorithm. At some point the algorithm must either output 0 or 1 as the first digit of the real number (any other output is clearly incorrect, and the algorithm is assumed to be total). If the algorithm outputs 1, I make my sequence become strictly less than 1, and if the algorithm outputs 0 I make my sequence become strictly greater than 1. Either way I have tricked the algorithm into giving an incorrect answer. This argument is easy to formalize via Kleene's recursion theorem.
Practically everything in the article is of a similar level of triviality. The material is thoroughly discussed by the books referenced at the end. CMummert · talk 21:41, 14 February 2007 (UTC)