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 any of them. Right?

  • 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... – Dims Aug 8 '13 at 13:43
  • Please do not use the "number-theory" tag on questions like this, which are not about number theory. – Carl Mummert Aug 8 '13 at 19:25
up vote 19 down vote accepted

Chaitin's constant is an example (actually a family of examples) of a noncomputable 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.

  • 1
    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$. – MJD Aug 8 '13 at 13:52
  • 5
    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. – Carl Mummert Aug 8 '13 at 19:23
  • 1
    @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$. – Carl Mummert Aug 8 '13 at 20:31
  • 3
    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). – Carl Mummert Aug 8 '13 at 20:35
  • 1
    The idea behind the Wikipedia article's claim is that one might try to "randomly generate" a program by repeatedly flipping a fair coin to generate a sequence $f \in 2^\omega$ and looking to see if any finite prefix of that $f$ is in the domain of a fixed universal prefix-free function $U$. But not all $f$ may have a prefix in the domain of $U$, in which case the claim that the process generates a "random program" breaks down, and makes one realize the more fundamental question of what a "program" for a universal prefix-free function is supposed to be, if that process is going to generate one. – Carl Mummert Aug 8 '13 at 20:41

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.

  • 10
    (+1) I like this answer because it explicitly provides a great many initial digits of an uncomputable real number and has a very simple easy-to-understand definition. The current state of knowledge about the max-shifts function is that $BB(5) \ge 47176870$, so the present example is actually 0.51562547683715820312500000000000616297582203915472977912941627176741932192527428924222476780414581298828125000..., where there are at least $\lfloor 47176870 \ log_{10}2\rfloor - 107 = 14201545$ zeros after the $...8125$ and before the next positive digit. – r.e.s. May 31 '14 at 13:52
  • 4
    Every finite sequence of digits is the start of the decimal expansion of an uncountable family of non-computable numbers – MJD May 31 '14 at 18:50
  • 1
    That's true, of course; but it's beside the point, which is that this particular uncomputable number (viz., $\sum_{i=1}^\infty 2^{-BB(i)}$) has these particular digits. – r.e.s. Jun 1 '14 at 4:29
  • 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. – mafu Dec 17 '14 at 15:50
  • 1
    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. – HasFiveVowels Feb 17 '17 at 18:40

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.

  • Would this example be more or less equivalent to the busy beaver example given by MJD? – k_g Dec 18 '14 at 3:03
  • 5
    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. – Denis Dec 18 '14 at 13:28
  • 2
    Love this answer. – charles Jan 19 '15 at 14:07
  • 1
    This is hilarious and yet at the same time useless to the reader. – Mark C Oct 20 '17 at 7:25

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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