14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Relavant: math.stackexchange.com/q/1266587/294695 $\endgroup$ – John Coleman May 13 '18 at 13:54
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Chaitin's_constant $\endgroup$ – chi May 13 '18 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$ – quetzalcoatl May 14 '18 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 '18 at 15:16
  • $\begingroup$ @JimmyJames, I did my best to translate it from Russian: Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Hope somebody will improve my translation. $\endgroup$ – fresheed May 14 '18 at 20:55
18
$\begingroup$

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":

func(number):
    return number

and call func(皮)

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 :-)

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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