Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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(皮)
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 :-)
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.
Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Hope somebody will improve my translation. $\endgroup$