Print 1 followed by googolplex number of zeros

Assuming we are not concerned about running time of the program (which is practically infinite for human mortals) and using limited amount of memory (2^64 bytes), we want to print out in base 10, the exact 开发者_开发知识库value of 10^(googolplex), one digit at a time on screen (mostly zeros).

Describe an algorithm (which can be coded on current day computers), or write a program to do this. Since we cannot practically check the output, so we will rely on collective opinion on the correctness of the program.

NOTE : I do not know the solution, or whether a solution exists or not. The problem is my own invention. To those readers who are quick to mark this offtopic... kindly reconsider. This is difficult and bit theoretical but definitely CS.

This is impossible. There are more states (10^(10^100)) in the program than there are electrons in the universe (~10^80). Therefore, in our universe, there can be no such realization of a machine capable of executing the task.

First of all, we note that 10^(10^100) is equivalent to ((((10^10)^10)^...)^10), 100 times.

Or 10↑↑↑↑↑↑↑↑↑↑10.

This gives rise to the following solution:

print 1
for i in A(10, 100)
    print 0

in bash:

printf 1
while true; do 
  printf 0
done

... close enough.

Here's an algorithm that solves this:

 print 1
 for 1 to 10^(10^100)
      print 0

One can trivially prove correctness using Hoare logic:

1. There are no pre-conditions
2. The post condition is that a one followed by 10^(10^100) zeros are printed
3. The cycle's invariant is that the number of zeros printed so far is equal to i

EDIT: A machine to solve the problem needs the ability to distinguish between one googolplex of distinct states: each state is the result of printing one more zero than the previous. The amount of memory needed to do this is the same needed to store the number one googolplex. If there isn't that much memory available, this problem cannot be solved.

This does not mean it isn't a computable problem: it can be solved by a Turing machine because a Turing machine has a limitless amount of memory.

There definitely is a solution to this problem in theory, assuming of course you have a machine that is capable of producing that sort of output. I'm pretty sure that a googolplex is larger than the number of atoms in the universe, at least according to what the physicists tell us, so I don't think that any physically realizable model of computation could print it out. However, mathematically speaking, you could define a Turing machine capable of printing out the value by just giving it a googolplex-ish number of states and having each write a zero and then move to the next lower state.

Consider the following:

• The console window to which you are printing the output will have a maximum buffer size.
• When this buffer size is exceeded, anything printed earlier is discarded, and the user will not be able to scroll back to see it.
• The maximum buffer size will be minuscule compared to a googolplex.

Therefore, if you want to mimic the user experience of your program running to completion, find the maximum buffer size of the console you will print to and print that many zeroes.

Hurray laziness!