Печать 1 с последующим числом нулей googolplex

Question

Предполагая, что мы не обеспокоены временем выполнения программы (которое практически бесконечно для смертных людей) и использованием ограниченного объема памяти (2 ^ 64 байта), мы хотим вывести в базу 10 точное значение 10^ (googolplex), одна цифра за раз на экране (в основном нули).

Опишите алгоритм (который может быть закодирован на современных компьютерах) или напишите программу для этого.Поскольку мы практически не можем проверить вывод, поэтому мы будем полагаться на коллективное мнение о правильности программы.

ПРИМЕЧАНИЕ. Я не знаю решение, существует ли решение или нет.Проблема в моем собственном изобретении.Тем читателям, которые быстро отмечают этот оффтоп ... любезно пересмотрим.Это сложно и немного теоретически, но определенно CS.

Answer 1

Это невозможно. В программе больше состояний (10 ^ (10 ^ 100)), чем электронов во вселенной (~ 10 ^ 80). Поэтому в нашей вселенной не может быть такой реализации машины, способной выполнить задачу.

Answer 2

Прежде всего отметим, что 10 ^ (10 ^ 100) эквивалентно ((((10 ^ 10) ^ 10) ^ ...) ^ 10), 100 раз.

или 10 ↑↑↑↑↑↑↑↑↑↑ 10.

Это приводит к следующему решению:

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

Answer 3

в Баш:

printf 1
while true; do 
  printf 0
done

... достаточно близко.

Answer 4

Вот алгоритм, который решает это:

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

Тривиально доказать правильность можно с помощью логики Хора :

1. Нет предварительных условий
2. Условие публикации: один, за которым следуют 10 ^ (10 ^ 100) нулей, печатаются
3. Инвариант цикла состоит в том, что количество напечатанных нулей до сих пор равно i

РЕДАКТИРОВАТЬ: машина для решения проблемы нуждается в способности различать один googolplex различных состояний: каждое состояние является результатом печати еще один ноль, чем предыдущее. Объем памяти, необходимый для этого, соответствует количеству one googolplex . Если памяти недостаточно, эта проблема не может быть решена.

Это не означает, что это не вычислимая проблема: она может быть решена машиной Тьюринга, потому что машина Тьюринга имеет неограниченный объем памяти.

Answer 5

Рассмотрим следующее:

• Окно консоли, в которое вы печатаете вывод, будет иметь максимальный размер буфера.
• При превышении этого размера буфера все напечатанное ранее отбрасывается, и пользователь не сможет прокрутить назад, чтобы увидеть его.
• Максимальный размер буфера будет минимальным по сравнению с гуголплексом.

Поэтому, если вы хотите имитировать пользовательский опыт работы программы до ее завершения, найдите максимальный размер буфера консоли, на которую вы будете печатать, и напечатайте столько нулей.

Ура лень!

Answer 6

Определенно, есть решение этой проблемы в теории, при условии, конечно, что у вас есть машина, способная производить такую ​​продукцию. Я почти уверен, что гуголплекс больше, чем число атомов во вселенной, по крайней мере, в соответствии с тем, что говорят нам физики, поэтому я не думаю, что какая-либо физически реализуемая модель вычислений могла бы его распечатать. Однако, математически говоря, вы можете определить машину Тьюринга, способную распечатывать значение, просто задав ему число состояний googolplex-ih, и каждое из них записывает ноль, а затем переходит в следующее более низкое состояние.