Talk:Computable number

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

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

I think I understand now. Thanks a lot.--80.136.136.219 22:14, 10 August 2005 (UTC)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

The article says, "That the computable numbers are at most countable intuitively comes from the fact that they are produced by Turing machines, of which there are only countably many." But the definition used of computable number says that N is computable if for any number n, there exists a Turing machine that produces the first n digits of N. This doesn't guarantee any Turing machine exists that produces N. (To see this, consider the equivalent "proof" that the reals are a subset of the rationals: For any real number N, for any number n, there exists a ratio which has the same first n digits as N.)

This proof applies instead to Alan Turing's original definition of computable numbers, which is entirely different: "The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means." ("On computable numbers, with an application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, ser. 2, vol. 42 (1936-?), pp.230-265.)

HOWEVER, Turing immediately goes on to say that pi and e are computable, even though their expressions as a decimal are not calculable by finite means. Turing's second definition in his paper says that the binary output produced by a machine is called the number computed by the machine, that a machine is "circle-free" if its output is of infinite length, and that a sequence is computable if it "can be" computed by a circle-free machine.

This clears up the contradiction: pi is then computable, and the computable numbers are enumerable because they are, in fact, the (infinite) outputs of Turing machines. But it is very counter-intuitive: it defines the "computable" numbers so that they cannot be computed in finite time, which is the exact opposite of what Turing said his intention was! I'm not sure how this should be cleared up, but the combination of definitions and proof on this page is incorrect. Philgoetz (talk) 01:55, 15 February 2016 (UTC)[reply]

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)[reply]

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.

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)[reply]

“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)[reply]

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]

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)[reply]

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)

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)[reply]

While I'm in a huffing mood, I huffed that too. -Dan 14:09, 6 June 2006 (UTC)

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 (a_n)_n where a_n = 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|. --Lambiam ^Talk 21:42, 17 June 2006 (UTC)[reply]

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)[reply]

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

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)[reply]

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)[reply]

Examples

Does anyone have examples of computable numbers? I assume all rational numbers are, but are pi or the square root of 2? --Maltelauridsbrigge (talk) 16:29, 5 August 2008 (UTC)[reply]

Yes, they are. Please see the French article. Bests--81.208.125.60 (talk) 18:58, 30 September 2008 (UTC)[reply]

What about examples of non-computable numbers? For example, is it possible to write down a series that is bounded but not by any computable number? Cesiumfrog (talk) 10:24, 25 January 2011 (UTC)[reply]

Sure, assuming you mean the least upper bound is not computable. In fact you can even do that computably. Start running all Turing machines "in parallel" (e.g. let the first one run for one cycle, then the second one for one cycle, go back to the first one, then second, then third, then first, second, third, fourth, etc). Whenever one finishes, add a new number to your sequence, a number of the form .0100111101000.... or whatever where you have a 1 in every location corresponding to a Turing machine that has finished up to that point.

In the end, you have a sequence whose least upper bound codes a solution to the halting problem, and is therefore not computable. --Trovatore (talk) 18:01, 25 January 2011 (UTC)[reply]

Online book is now gone

I've removed the following external link from the article:

http://www.informatik.fernuni-hagen.de/thi1/klaus.weihrauch/book.html

This link doesn't work anymore, and a quick Google search didn't turn up an online copy (freely readable) anywhere. Please correct me if I'm wrong. - dcljr (talk) 03:01, 2 August 2009 (UTC)[reply]

"Many" definable, noncomputable real numbers?

The article states: "There are many definable, noncomputable real numbers" and proceeds to show just a couple of proof-of-concept non-computables, both defined on top of the halting problem. That is hardly many. Notice the keyword definable in the sentence, which excludes any collective, measure theoretic result, such as cardinal implications.

Later, it says: "The computable numbers include many of the specific real numbers which appear in practice". It should be saying "all of the real numbers which appear in practice", as there can be no real number which appears in practice but is not computable, if by "practice" you exclude toying with proof-of-concepts about the halting problem. This is such an important point about the whole matter of computable numbers that I would put it in the opening paragraph.

What say you?

Etatoby (talk) 01:52, 14 November 2011 (UTC)[reply]

Well, that's just wrong. For example the real number 0' is uncomputable, and appears in practice, at least if we mean the practice of computability theorists. --Trovatore (talk) 08:34, 14 November 2011 (UTC)[reply]

Add any computable number to a noncomputable number and one gets another noncomputable number so it is pretty easy to define lots and lots of noncomputable numbers. You'd also have to exclude numbers which may or may not exist like the highest twin primes and many other conjectures which may be insolvable. Dmcq (talk) 11:13, 14 November 2011 (UTC)[reply]

This risks to drift off-topic, but I don't quite understand your second sentence. If there is a greatest pair of twin primes, they are certainly computable. All integers yes, Bo, I mean the corresponding integer reals are computable.

Trying to read your mind a little, could you be thinking that there may not be a computer program that we can look at and say, I can see that this program will halt and tell us what is the largest twin prime? But there doesn't have to be. For a number to be computable, a program computing it has only to exist. It doesn't have to be provably correct. --Trovatore (talk) 20:14, 14 November 2011 (UTC)[reply]

Sorry yes my mistake. Dmcq (talk) 12:45, 15 November 2011 (UTC)[reply]

You know, this confusion comes up often enough that it might be worth saying something about it in the article, if a source can be found. I'd like to make a point along these lines (I'm not going to try to put it in encyclopedic style here, just give a sketch of the sort of content I'd like to see):

Let n be defined as follows: n=1 if the continuum hypothesis holds, 0 if not. Is n computable? Yes; n is either 1 or 0, and both 1 and 0 are computable. The actual programs that witness that 1 and 0 are computable have nothing to do with the continuum hypothesis, but that does not in any way affect the conclusion that n is computable.

Surely there's a source out there somewhere that has made this point. --Trovatore (talk) 20:33, 16 November 2011 (UTC)[reply]

According to Google books your example (specifcally mentioning the continuum hypothesis) is on page viii of Computability: a mathematical sketchbook by Bridges. He casts it as a constant function rather than a computable number, but that is a triviality. — Carl (CBM · talk) 03:41, 17 November 2011 (UTC)[reply]

Thanks, Carl, that might work. --Trovatore (talk) 03:53, 17 November 2011 (UTC)[reply]

order-isomorphic to rationals

Vladimir has added a note that the computable reals are order-isomorphic to the rationals. That's true, of course, because all countable dense linear orders without endpoints are order-isomorphic to the rationals. My concern is that the text as written makes this sound like something too special about the computable reals, when it's really a trivial observation when you know the result in my previous sentence.

We could explicitly say that, but then my objection is that it's not clear why we bring it up. I just don't think it's a very interesting property of the computable reals per se. --Trovatore (talk) 01:35, 28 December 2011 (UTC)[reply]

Since every countable subfield of the reals has this property, I think that it's enough for this article to just point out that the computable numbers are a countable subfield. The same goes for other properties like having characteristic zero. — Carl (CBM · talk)

Are computable numbers computably enumerable?

The section Properties says: "Although the computable numbers are an ordered field, the set of Gödel numbers corresponding to computable numbers is not itself computably enumerable, because it is not possible to effectively determine which Gödel numbers correspond to Turing machines that produce computable reals." However, as it is mentioned in this talk page earlier, one can run all possible Turing machines in parallel (executing sequentially one step of each machine and adding new machines after every round). Each machine which produces computable number halts in finite number of steps, so using this method one can effectively enumerate as many computable reals as desired. If so, the set of Turing machines that produce computable reals seems to be computably enumerable, although it is not computable. Is there a mistake in the article or am I wrong in my understanding? 77.254.193.94 (talk) 19:10, 19 August 2012 (UTC)[reply]

A computable real number is in general infinite, not finite, so it is not the case that "each machine which produces computable number halts in finite number of steps". — Carl (CBM · talk) 19:36, 19 August 2012 (UTC)[reply]

Complex number

"A complex number is called computable if its real and imaginary parts are computable." Is that an if and only if? If not, is there a fun counterexample? SamuelRiv (talk) 07:05, 7 September 2012 (UTC)[reply]

This statement has the form of a definition. Conventionally in mathematics, definitions use if, not if and only if. The if is not to be thought of as a logical connective, because a definition is not a proposition at all, but something more like an assignment in a programming language. --Trovatore (talk) 07:15, 7 September 2012 (UTC)[reply]

Dedekind cuts?

This article currently reads: A real number is computable if and only if there is a computable Dedekind cut D converging to it. Naively, this seems to contradict the idea behind the Specker sequence. Can someone elaborate, or provide a reference? User:Linas (talk) 20:49, 3 September 2013 (UTC)[reply]

One can surely dig out references (e.g Hirst, Representations of Reals in Reverse Mathematics [1] or one of the many references in Weirauch-style computable analysis). The answer to your implicit question is that there is not a computable Dedekind cut for a real α that is the limit of a Specker sequence, as the set

\{q\in \mathbb {Q} :q>\alpha \}

is not computable. — Carl (CBM · talk) 23:04, 3 September 2013 (UTC)[reply]

§ Properties

I think § Properties should be changed to

"While the set of real numbers is uncountable, the set of computable numbers is only countable and thus almost all real numbers are not computable. The computable numbers can be counted by assigning a Gödel number to each Turing machine definition. This gives a function from the naturals to the computable reals. Although the computable numbers are an ordered field, the set of Gödel numbers corresponding to computable numbers is not itself computably enumerable, because it is not possible to effectively determine which Gödel numbers correspond to Turing machines that produce computable reals. In order to produce a computable real, a Turing machine must compute a total function, but the corresponding decision problem is in Turing degree 0′′. Thus Cantor's diagonal argument cannot be used to produce uncountably many computable reals; at best, the reals formed from this method will be uncomputable. There are only countably many algorithms and so there can only be countably many computable numbers.

It might seem like a brain can generate an uncomputable number by using Cantor's diagonal argument on all computable numbers and so compute a number a computer can't. The mistake in that argument is that not all algorithms generate a number at all and you don't know which algorithms generate a number to apply Cantor's diagonal argument to them. When ever you think of a way to generate a sequence of numbers in your head, only some of the algorithms that generate a number generate a number from that sequence and not all of them. You can apply Cantor's diagonal argument to generate a number not appearing anywhere in that sequence in your head and try to generate another sequence of all numbers you can easily think of a way to generate in terms of that sequence. That will exhaust more of the algorithms that do generate a number but there will still be some left so that doesn't prove applying Cantor's diagonal argument to that sequence will generate an uncomputable number in your head. We're pretty sure it will be computable in all new situations where you think of a way to generate a number in your head because there are some computer science experts who have never thought of a way to generate a number in their head without being able to find an algorithm that generates it, though we can never completely prove that a brain can't generate an uncomputable number. Just because a brain can only generate computable numbers doesn't mean uncomputable numbers don't exist. We know that they exist because we can define one in terms of which algorithms generate a number despite the fact that we don't know which ones do. For example, take a sequence of all algorithms that generate a number then replace each algorithm in the sequence with the number it generates, then Cantor's diagonal argument tells us that there exists a number not in that sequence which is therefore uncomputable.

The arithmetical operations on computable numbers are themselves computable in the sense that whenever real numbers a and b are computable then the following real numbers are also computable: a + b, a - b, ab, and a/b if b is nonzero. These operations are actually uniformly computable; for example, there is a Turing machine which on input (A,B, $\epsilon$ ) produces output r, where A is the description of a Turing machine approximating a, B is the description of a Turing machine approximating b, and r is an $\epsilon$ approximation of a+b.

The computable real numbers do not share all the properties of the real numbers used in analysis. For example, the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number (Bridges and Richman, 1987:58). A sequence with this property is known as a Specker sequence, as the first construction is due to E. Specker (1949). Despite the existence of counterexamples such as these, parts of calculus and real analysis can be developed in the field of computable numbers, leading to the study of computable analysis.

The order relation on the computable numbers is not computable. There is no Turing machine which on input A (the description of a Turing machine approximating the number $a$ ) outputs "YES" if $a>0$ and "NO" if $a\leq 0$ . The reason: suppose the machine described by A keeps outputting 0 as $\epsilon$ approximations. It is not clear how long to wait before deciding that the machine will never output an approximation which forces a to be positive. Thus the machine will eventually have to guess that the number will equal 0, in order to produce an output; the sequence may later become different from 0. This idea can be used to show that the machine is incorrect on some sequences if it computes a total function. A similar problem occurs when the computable reals are represented as Dedekind cuts. The same holds for the equality relation : the equality test is not computable.

While the full order relation is not computable, the restriction of it to pairs of unequal numbers is computable. That is, there is a program that takes an input two Turing machines A and B approximating numbers a and b, where a≠b, and outputs whether a<b or a>b. It is sufficient to use ε-approximations where $\varepsilon <|b-a|/2$ so by taking increasingly small ε (with a limit to 0), one eventually can decide whether a<b or a>b.

Every computable number is definable, but not vice versa. There are many definable, noncomputable real numbers, including:

The binary representation of the halting problem (or any other uncomputable set of natural numbers).
Chaitin's constant, $\Omega$ , which is a type of real number that is Turing equivalent to the halting problem.

Both of these examples in fact define an infinite set of definable, uncomputable numbers, one for each Universal Turing machine. A real number is computable if and only if the set of natural numbers it represents (when written in binary and viewed as a characteristic function) is computable.

Every computable number is arithmetical.

The set of computable real numbers (as well as every countable, densely ordered subset of reals without ends) is order-isomorphic to the set of rational numbers."

Can anyone find sources for the information I added. If not then maybe find an expert to discuss whether what I added is true and if they say it's true, it almost definitely is true which satisfies the original purpose of Wikipedia:No original research and so maybe it doesn't need to be cited even if it's suspected that no sources exist. The article probably would satisfy the less strict criterion of Wikipedia:Verifiability because so many computer scientists reading the article could verify that information by figuring out that it's true. See Wikipedia:Ignore all rules. Blackbombchu (talk) 04:42, 23 November 2014 (UTC)[reply]

is $[0,1]$ $2^{\omega }$ correct?

I just cleaned up the language in section Computable_number#Digit_strings_and_the_Cantor_and_Baire_spaces, and I wondered about the sentence: " While $[0,1]$ $2^{\omega }$ is totally disconnected …". Does this make sense? I would have expected " While $2^{\omega }$ is totally disconnected". Atoll (talk) 06:23, 23 September 2022 (UTC)[reply]

My guess is, just an editing mistake. I've fixed it. If it wasn't a mistake, then hopefully someone will make it known. --Trovatore (talk) 06:28, 23 September 2022 (UTC)[reply]

A similarly weird expression is still remaning, viz. "

\mathbb {R}

\omega ^{\omega }

". Each of these expressions used two <math> tags in the source code. Possibly, the editor had meant "

[0,1]

alias

2^{\omega }

" and "

\mathbb {R}