27
$\begingroup$

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!

$\endgroup$
4
  • 6
    $\begingroup$ 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. $\endgroup$
    – Mauro ALLEGRANZA
    Feb 6, 2014 at 19:22
  • $\begingroup$ 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. $\endgroup$
    – Phira
    Feb 7, 2014 at 10:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – CoolHandLouis
    Feb 7, 2014 at 13:38
  • $\begingroup$ @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. $\endgroup$
    – anon
    Feb 7, 2014 at 21:50

2 Answers 2

Reset to default
33
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This makes perfect sense. Thanks! $\endgroup$
    – joker
    Feb 6, 2014 at 19:23
  • $\begingroup$ I wasn't familiar with that thing. Interesting! $\endgroup$
    – Balarka Sen
    Feb 6, 2014 at 19:25
  • $\begingroup$ @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 ? $\endgroup$
    – Mauro ALLEGRANZA
    Feb 10, 2014 at 11:02
  • $\begingroup$ @MauroALLEGRANZA: Chaitin's constant is uncomputable because not one single program can generate all its digits. However, for each desired precision there is a program that can generate it to that precision. So a definable number may not be computable, which appears to be the way you are talking about "knowable". It is the same reason why the halting problem has a definable answer, though not computably definable. So actually "perfect secrets" are a strict subset of uncomputable numbers. $\endgroup$
    – user21820
    Nov 25, 2015 at 6:12
  • 1
    $\begingroup$ @MauroALLEGRANZA: Sorry my comment was not quite correct either. Obviously for every number and desired precision there is a program that can generate it to that precision, so I'm not really saying anything about Chaitin's constant. What I should have said is that there is a computable sequence of programs such that the numbers computed by that sequence form a sequence converging to Chaitin's constant. This does not mean that Chaitin's constant is computable because we don't know how far in that sequence we have to go to get some desired precision. $\endgroup$
    – user21820
    Nov 25, 2015 at 6:25
23
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ great explanation, thanks! $\endgroup$
    – joker
    Feb 6, 2014 at 19:29
  • 1
    $\begingroup$ regarding your last paragraph: algorithms can also take (real) arguments, though, so wouldn't there be uncountably many algorithm-argument combinations? $\endgroup$
    – wchargin
    Feb 7, 2014 at 0:34
  • 9
    $\begingroup$ @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...). $\endgroup$
    – Steve Jessop
    Feb 7, 2014 at 1:17
  • $\begingroup$ Okay, that makes sense; thanks. $\endgroup$
    – wchargin
    Feb 7, 2014 at 5:02
  • $\begingroup$ 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. $\endgroup$
    – Magdiragdag
    Feb 7, 2014 at 7:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .