Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia states: "The computable numbers include many of the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, π, and many other transcendental numbers."

I remember my professor saying incomputable numbers are transcendental. Is this so? Or am I to suggest that some transcendental numbers such as π and e are computable but others are not. If so are there any examples of transcendental numbers that are not computable? Or any numbers which are not computable?

Thanks in advance!

share|improve this question
6  
Computable real numbers are countable; real numbers are uncountable: so there are planty of incomputable real numbers. If a real number is algebraic, you can find an algorithm to generate its infinite approximation, so it is computable. Also trascendental numbers that are "known" has some way of approximating them, so ara computable. –  Mauro ALLEGRANZA Feb 6 at 19:22
    
Is it obvious that it is impossible to define a real number in a way that makes it undecidable if it is computable and algebraic? In that case, it would be perfectly possible to have an algebraic number that is not computable. All the answers seem to assume that the numbers are either given by their polynomials or known to be algebraic. –  Phira Feb 7 at 10:20
1  
Sure, here's an example of a non-computable transcendental number: 5.3817361849593022472531056235246743534429660488238856364542... That's the start of it... I'll have to come back and complete this answer later. –  CoolHandLouis Feb 7 at 13:38
    
@Phira All that matters is that there exists a computational procedure for approximating a number to any specified precision, whether or not we know the number has the procedure or not. –  anon Feb 7 at 21:50
add comment

2 Answers 2

up vote 28 down vote accepted

Any algebraic number is computable; just employ approximation algorithms to obtain roots to any desired level of precision. Therefore, contrapositively, uncomputable numbers are transcendental.

An example of a number that is not computable is Chaitin's constant. Being able to compute it would yield a solution to the Halting Problem, which is undecidable, so we can't. Technically the constant depends on choice of programming language or universal Turing machine (I'm not entirely clear on the details there), so there are a whole suite of uncomputables in this way.

share|improve this answer
    
This makes perfect sense. Thanks! –  joker Feb 6 at 19:23
    
I wasn't familiar with that thing. Interesting! –  Balarka Sen Feb 6 at 19:25
    
@anon & joker - I will try with a "metaphor". A "known fact" is something that we can "speak of"; a "perfect secret" is something that nobody can "speak of". Mathematicians "knows" a trascendental number when they have an algorithm to obtain an approximation of it. So uncomputable numbers are "perfect secret" numbers, numbers which we are not able to "speak of". If this metaphor is not measleading, what about Chaitin's constant ? Do we "know" it ? –  Mauro ALLEGRANZA Feb 10 at 11:02
add comment

Yes, every incomputable number is transcendental, or, differently said, every algebraic number is computable. (Because it is possible to compute an arbitrary close rational approximation to every algebraic number).

As you noted, not every transcendental is incomputable. Consider for instance $0.101001000100001\dots$ (or $\pi$ or $e$).

A counting argument shows that nearly all numbers are incomputable: there are only countable many algorithms, so only countable many computable numbers, but there are uncountable many real (or complex) numbers.

share|improve this answer
    
great explanation, thanks! –  joker Feb 6 at 19:29
    
regarding your last paragraph: algorithms can also take (real) arguments, though, so wouldn't there be uncountably many algorithm-argument combinations? –  WChargin Feb 7 at 0:34
7  
@WChargin: no, finite computation models do not allow algorithms that take as input an arbitrary real number. If you're using some unusual computation model that acts on arbitrary reals, then I guess it allows arbitrary real constants, so trivially all reals are computable (and inputs/outputs/programs in this computation model cannot generally be written on paper...). –  Steve Jessop Feb 7 at 1:17
    
Okay, that makes sense; thanks. –  WChargin Feb 7 at 5:02
    
There is a notion of computable functions on reals. You see reals, for instance, as streams of ever shrinking (to size 0) rational intervals and such a function produces such a stream as well - every time it receives another interval from the input stream it produces a new interval in the output stream. The identity function $\text{id} \colon {\mathbb R} \to {\mathbb R}$ is computable in this sense; but a constant function that (always) outputs a non-computable real still isn't. –  Magdiragdag Feb 7 at 7:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.