1の後にgoogolplexの0の数が続きます

Question

プログラムの実行時間（実際には人間の人にとって無限大です）と限られた量のメモリ（2^64バイト）を使用することを心配していないと仮定して、基数10、10 ^（googolplex）の正確な値。一度に1桁ずつ画面上に表示されます（ほとんどゼロ）。

アルゴリズム（現在のコンピュータにコード化できる）を記述するか、またはこれを行うプログラムを記述します。 実際に出力を確認することはできないため、プログラムの正しさについての意見集に頼ります。

注：私は解決法、または解決策が存在するかどうかを知りません。問題は私自身の発明です。このofftopicを素早くマークする読者に...親切に再考してください。これは難しく、少し理論的ですが、間違いなくCSです。ここで

Answer 1

これは不可能です。プログラムには、宇宙の電子（〜10^80）よりも多くの状態（10 ^（10^100））があります。したがって、私たちの宇宙では、そのタスクを実行することができる機械のそのような実現はあり得ません。

Answer 2

はこれを解くアルゴリズムです：

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

一つは自明Hoare logicを使用して正しさを証明することができます。

1. 一切の前提条件
2. はありませんポスト条件は1が続いていることです10 ^（10^100）のゼロが印刷されます
3. サイクルの不変量は、今までに印刷されたゼロの数がi

編集：問題を解決するマシンでは、異なる状態のグーグルプレックスを区別する能力が必要です。各状態は、以前のものより1つ多くゼロを印刷した結果です。これを行うのに必要なメモリ量は、番号googolplexを格納するのに必要なものと同じです。使用可能なメモリがあまりない場合、この問題は解決できません。

これは計算上の問題ではないことを意味するわけではありません。チューリングマシンは無限のメモリ容量を持つため、チューリングマシンで解決できます。

Answer 3

もちろん、理論上この問題の解決策があります。もちろん、そのような出力を生成できるマシンがあるとします。物理学者が私たちに言うことによれば、少なくともgoogolplexは宇宙の原子の数よりも大きいので、物理的に実現可能な計算モデルはそれを印刷することはできないと私は考えていません。しかし、数学的に言えば、Googolplex-ish数の状態を与え、各書き込みを0にしてから次の低い状態に移動するだけで、値を印刷できるチューリングマシンを定義できます。

Answer 4

まず、10 ^（10^100）は（（（10^10）^ 10）^ ...）^ 10）、100回に相当することに注意してください。

または10↑↑↑↑↑↑↑↑↑↑10。

これは、次の解決策を生じさせる：十分に近い...

printf 1 
while true; do 
    printf 0 
done 

：bashで

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

Answer 5

。

Answer 6

は、次のことを考えてみましょう：

• あなたが出力を印刷していると、コンソールウィンドウが最大バッファサイズを持つことになります。
• このバッファサイズを超えると、以前に印刷されたものはすべて破棄され、ユーザーはそれを見るためにスクロールバックできなくなります。
• 最大バッファサイズはgoogolplexに比べて非常に小さくなります。

したがって、あなたは、完了するまで実行しているプログラムのユーザーエクスペリエンスを模倣するあなたに印刷し、多くのゼロということに印刷されますコンソールの最大バッファサイズを検索する場合。

ハレイ怠惰！