I have the problem:

Show that there exists a real number for which no program exists that runs infinitely long and writes that number's decimal digits.

I suppose it can be solved by reducing it to the Halting problem, but I have no idea how to do so.

I would also appreciate links to similar problems for further practice.

  • $\begingroup$ Relavant: math.stackexchange.com/q/1266587/294695 $\endgroup$ May 13, 2018 at 13:54
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Chaitin's_constant $\endgroup$
    – chi
    May 13, 2018 at 16:43
  • $\begingroup$ Yuval Filmus provided interesting answer that you should carefully read. The halting problem "is the thing" that you may attempt to reduce to your problem, not the other way around (reduce your problem to halting - as you hypothesize in your question). $\endgroup$ May 14, 2018 at 9:14
  • $\begingroup$ Could this question be improved by correcting the grammar in the quoted section? I find it really difficult to parse. $\endgroup$
    – JimmyJames
    May 14, 2018 at 15:16
  • $\begingroup$ @JimmyJames, I did my best to translate it from Russian: Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Hope somebody will improve my translation. $\endgroup$
    – fresheed
    May 14, 2018 at 20:55

5 Answers 5


As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still must be other numbers.

By the way if the algorithm has (finite) arguments, you can just rewrite that as a "longer" list of programs where each program doesn't have any arguments.

With regard to your comment "What if real numbers are allowed as argument", then the question's premise is wrong: all numbers in R can then be generated. If someone finds a number, say 皮 and claims it cannot be computed, we have the following "algorithm":

    return number

and call func(皮)


It's actually much simpler. There's only a countable number of algorithms. Yet there are uncountably many real numbers. So if you try to pair them up, some real numbers will be left hanging.


Consider the number whose $k$th digit is $1$ if the $k$th Turing machine halts on the empty input, and $0$ if it doesn't halt. If you could generate the digits of this real number then you could solve the halting problem.


The number is an infinitelly long number which after decimal point encodes anyhow all the turing machines which don't halt. With this number, you would be able to solve halting problem.

You can "search" the TM in the number and run it in parallel. If TM halts, it halts. If not, you would "find its code in the number".

There are many modifications of the proof and you should be able to reproduce them after the very first complexity lesson :-)

  • $\begingroup$ This is closely related to Chaitin's constant. $\endgroup$ May 14, 2018 at 16:52
  • $\begingroup$ yah, bud much easier to understand... $\endgroup$
    – smrt28
    May 14, 2018 at 17:26

A point moves in a path by the funcion y = 2x. When the abscissa is a non computable number, there is no way for the Point to compute its path, but we know it goes on. So non computable numbers can exist at all.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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