79
$\begingroup$

Is this true, that if we can describe any (real) number somehow, then it is computable?

For example, $\pi$ is computable although it is irrational, i.e. endless decimal fraction. It was just a luck, that there are some simple periodic formulas to calcualte $\pi$. If it wasn't than we were unable to calculate $\pi$ ans it was non-computable.

If so, that we can't provide any examples of non-computable numbers? Is that right?

The only thing that we can say is that these numbers are exist in many, but we can't point to any of them. Right?

$\endgroup$
2
  • 1
    $\begingroup$ I can't be more precise since I don't know :) I agree that probably there can be some desriptions of non-computable numbers -- this is what my question about -- please provide some for me to feel... $\endgroup$
    – Dims
    Aug 8, 2013 at 13:43
  • 2
    $\begingroup$ Roll a ten sided die numbered 0-9 an infinite number of times. $\endgroup$
    – Michael
    May 20, 2019 at 3:13

6 Answers 6

Reset to default
96
$\begingroup$

I haven't thought this through, but it seems to me that if you let $BB$ be the Busy Beaver function, then $$\sum_{i=1}^\infty 2^{-BB(i)}=2^{-1}+2^{-6}+2^{-21}+2^{-107}+\ ... \ \approx 0.515625476837158203125000000000006$$ should be a noncomputable real number, since if you were able to compute it with sufficient precision you would be able to solve the halting problem.

$\endgroup$
5
  • 11
    $\begingroup$ Every finite sequence of digits is the start of the decimal expansion of an uncountable family of non-computable numbers $\endgroup$
    – MJD
    May 31, 2014 at 18:50
  • $\begingroup$ I recommend to specify you refer to the "shift" function, not Rado's Sigma. Even though it does not make a difference in practice, of course. $\endgroup$
    – mafu
    Dec 17, 2014 at 15:50
  • 1
    $\begingroup$ "sufficient" is a subjective term. "arbitrary" might be more appropriate - (I'm no expert though). $\endgroup$
    – user2820379
    Jan 27, 2015 at 3:31
  • 3
    $\begingroup$ "Sufficient" is not a subjective term; it is a mathematical term of art with a specific technical meaning. $\endgroup$
    – MJD
    Jan 27, 2015 at 5:18
  • 6
    $\begingroup$ While it's true that "sufficient" is a technical term and not necessarily incorrect, I believe "arbitrary" is more appropriate here. In order for a number to be computable, it needs to be able to be specified with arbitrary precision. "Sufficient" implies some threshold that you must cross. "Arbitrary" implies that that threshold is infinite. $\endgroup$
    – Tim
    Feb 17, 2017 at 18:40
50
$\begingroup$

Chaitin's constant is an example (actually a family of examples) of a non-computable number. It represents the probability that a randomly-generated program (in a certain model) will halt.

It can be calculated approximately, but there is (provably) no algorithm for calculating it with arbitrary precision.

$\endgroup$
13
  • 3
    $\begingroup$ Yes. You can obviously change the probability with which a random program halts by changing the programming language or computational model you are working in. But each language has its own associated $\Omega$. $\endgroup$
    – MJD
    Aug 8, 2013 at 13:52
  • 10
    $\begingroup$ An $\Omega$ number does represent something, but not (as the WIkipedia article also says) "the probability that a randomly generated program will halt", because (1) there is not any canonical probability measure on the set of programs, and (2) the non-canonical measure used to generate a particular $\Omega$ number may not be a probability measure. I realize I am being picky about this, but it is a common point of confusion in that area. $\endgroup$
    – Carl Mummert
    Aug 8, 2013 at 19:23
  • 4
    $\begingroup$ @MJD: An $\Omega$ number, relative to a universal prefix-free function $U$, is exactly the measure of the set of infinite binary sequences $f \in 2^\omega$ such that there is a finite prefix of $\sigma$ of $f$ on which $U$ will halt. The measure is the usual fair-coin probability measure on $2^\omega$, which is fixed and independent of $U$. $\endgroup$
    – Carl Mummert
    Aug 8, 2013 at 20:31
  • 3
    $\begingroup$ The key points: (1) The measure is on $2^\omega$, not on $2^{<\omega}$ or on "programs". (2) There is no useful probability measure on $2^{<\omega}$ or any countable discrete set. (3) It is not even clear what a "program" for a prefix-free universal function $U$ should be, since every string is a legal input for $U$. Is a "program" then an arbitrary string (in which case the set of programs is not prefix-free, and the infinite sum of $2^{-|p|}$ over all programs $p$ diverges) or is a "program" just an input on which $U$ halts (in which case the probability a "random program" halts is 1). $\endgroup$
    – Carl Mummert
    Aug 8, 2013 at 20:35
  • 3
    $\begingroup$ Reminder: Anyone can edit Wikipedia and make it better... $\endgroup$
    – Steve Kass
    May 29, 2014 at 3:05
43
$\begingroup$

Any language can be turned into a number, by setting the $i^{th}$ decimal to 1 if the $i^{th}$ word is in the language, and to 0 otherwise. So we can build for instance the number $H$, which describes the halting problem and is therefore uncomputable.

$\endgroup$
7
  • 1
    $\begingroup$ Would this example be more or less equivalent to the busy beaver example given by MJD? $\endgroup$
    – k_g
    Dec 18, 2014 at 3:03
  • 8
    $\begingroup$ Yes it is more or less the same idea up to encoding, which is basically the reason why we can exhibit uncomputable real numbers, because a real number can encode an undecidable language. $\endgroup$
    – Denis
    Dec 18, 2014 at 13:28
  • 2
    $\begingroup$ Love this answer. $\endgroup$
    – charles
    Jan 19, 2015 at 14:07
  • 5
    $\begingroup$ This is hilarious and yet at the same time useless to the reader. $\endgroup$
    – Mark C
    Oct 20, 2017 at 7:25
  • $\begingroup$ Can you really turn a language into a number with that procedure? I understand that you can create a string of bits that is infinite in length with this procedure. But a number with an infinite amount of bits? $\endgroup$
    – giusti
    Dec 6 at 2:49
8
$\begingroup$

I usually consider the function $f(n)=1$ if the $n^{th}$ computer program halts with input $0$ and $f(n)=0$ otherwise. The real number $r=\sum_{n\in \mathbb{N}} f(n)\times 2^{-n}$ must be non-computable, otherwise you would be able to solve the halting problem.

Note: in order to accept this argument you must accept that there is a bijection between natural numbers and computer programs, which can be easily done by assigning values to the symbols used to write programs.

$\endgroup$
2
$\begingroup$

Examples of uncomputable numbers, like the one clearly presented by Luis Fonsera, seem to assume that the halting of any particular Turing machine can be determined (by some other Turing machine ?). Is this always true? It not then for some values of n, Fonsera's function f(n) might not be determined and so the uncomputable number r is undetermined. An example might be a Turing machine that searches for violations of the Goldbach conjecture. Another could be a Turing machine, T, that searches through ratios of two rational numbers to see if it can find one that is squareroot of 2. We know that this programme wil never halt but I am at a loss to see how a Turing machine could come to show this just by examining the programme of machine T. Are some mathematical truths like the irrationality of squareroot 2 uncomputable?

$\endgroup$
2
$\begingroup$

Most finite strings of digits have high Kolmogorov complexity (Li & Vitanyi, 1997). This means they can not be produced by a Turing machine much smaller than the length of the string itself. There is a counting argument for this, which (overly simplified) says that there are less strings with length n-1 than there are with length n. If this is also the case for infinite strings (which I assume, but don't remember) it follows that most real numbers are uncomputable.

Li, Ming; Vitányi, Paul (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer.

$\endgroup$
1
  • 4
    $\begingroup$ You can show that there are uncountably many uncomputable real numbers more directly - there are only countably many Turing machines, so there are only countably many computable numbers, so there are uncountably many remaining real numbers that aren’t computable. $\endgroup$
    – templatetypedef
    May 24, 2022 at 15:19

You must log in to answer this question.

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