Seal 1 followed by googolplex number of zeros

Question

Assuming we are not interested in the running time of the program (which is almost endless for human mortals) and using a limited amount of memory (2 ^ 64 bytes), we want to print in base 10, the exact value 10 ^ (googolplex), one digit at a time on the screen (mostly zeros).

Describe the algorithm (which can be encoded on computers of the current day) or write a program for this. Since we cannot practically verify the exit, we will therefore rely on a collective opinion on the correctness of the program.

NOTE. I do not know the solution or whether there is a solution. The problem is my own invention. For those readers who quickly celebrate this offtopic ... kindly review. It is complex and theoretically, but definitely CS.

Answer 1

It's impossible. The program has more states (10 ^ (10 ^ 100)) than there are electrons in the Universe (~ 10 ^ 80). Therefore, in our universe there cannot be such an implementation of a machine that is capable of performing a task.

Answer 2

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

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

This leads to the following solution:

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

Answer 3

Here is an algorithm that solves this:

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

One can trivially prove correctness using the Logic of Chorus :

• No preconditions
• The post-condition is that it prints one after it zero 10 ^ (10 ^ 100)
• The loop invariant is that the number of zeros printed so far is i

EDITING: a machine to solve a problem requires the ability to distinguish one googolplex of different states: each state is the result of printing another zero than the previous one. The amount of memory required for this is the same as for storing the number one complex. If there is not enough available memory, this problem cannot be resolved.

This does not mean that this is not a computable problem: it can be solved using a Turing machine, since the Turing machine has an unlimited amount of memory.

Answer 4

in bash:

 printf 1 while true; do printf 0 done 

... close enough.

Answer 5

In theory, there is definitely a solution to this problem, assuming, of course, that you have a machine capable of producing this type of output. I am sure that googolplex is larger than the number of atoms in the Universe, at least in accordance with what physicists tell us, so I do not think that any physically feasible model of calculations could print it. However, mathematically speaking, you could define a Turing machine capable of printing a value by simply indicating to it the homogoplex number of states and each of them will write zero, and then move to the next lower state.

Answer 6

Consider the following:

• The console window on which you print the output will have a maximum buffer size.
• When this buffer size is exceeded, everything that was previously printed is discarded, and the user will not be able to scroll back to see it.
• The maximum buffer size will be small compared to googolplex.

Therefore, if you want to imitate the user experience of your program running before completion, find the maximum size of the console buffer you will print to and print a lot of zeros.

Urai laziness!