は、このプログラム停止

Question

は、私は厳格なコンピュータサイエンスの観点から正しい答えは何だろう。

int main() 
{ 
    Generator gen; // True random generator returning 0 or 1 with 50% probability  each 
    while (gen() == 0); 
} 

Answer 1

チューリングマシンモデルを使用してこの状況をモデル化することは困難です。

なぜですか？まあ、チューリングマシンはチャンスを取らない。非決定的なTMがありますが、そこにはチャンスはありません。 NTMは、同じ構成で常に同じ動作をする確定的なTMより強力ではありません。したがって、計算にチャンスを注入しようとすると、TM自体の仕組みに注入することは困難です。

別の可能性は、TMに入力されたテープであることをRNGの出力を考慮することです。 TMのテープはバイナリ文字列です。あなたの質問は次のように再フォーマットできます：00 ... 0 ...チューリングマシンへの入力のための有効な無限バイナリ文字列？

1. 00 ... 0 ...有効なRNG出力はありますか？
2. 00 ... 0 ... TMへの有効な入力？

ランダム性に対する最新の情報理論的アプローチは、ネガティブな最初の質問に答えます。シーケンス00 ... 0 ...は低エントロピーを有し、while true print 1 loopによって精密に記述することができる。そのサンプル分布は、大多数の法則や中心極限定理と一致しません。出力に基づいて、現代のアプローチは、ランダムなソースから来ていない文字列、RNGが真のランダムソースであると仮定したので矛盾を特徴づけるだろう。だから00 ... 0 ...私たちのソースによって生成されていません。それは形式言語であるように基づくチューリングマシンの

標準的な定義は、通常、テープ上にあるように、入力の無限の量を認めていません。つまり、無限の回数だけ現れるのは、空白のシンボルだけです。さて、ブランクシンボルを0と解釈し、入力シンボルを1にすることは許されますが、入力にはブランクが入りますが、これは許可されません。入力。この場合、私は質問が停止鶏の問題に類似していると主張したいと思います：チキンを入力すると、TMは停止しますか？そしてその答えも同様です。

要約：この問題に対する厳密なアプローチについての私の推測は、 です.RNGは00 ... 0 ...を生成できません。生成できるすべての文字列に対してTMが停止するため、TMは停止します。または - 00から0へのTMの適用は未定義です。 「厳格なコンピュータ科学の視点」から

Answer 2

は、あなたの質問にはバグがあります：Cコンパイラからアクセスなし「真の乱数発生器」とは、あなたのコードの形で暗示一つとしてありません。

あなたのCコンパイラが実際にgen（）関数を呼び出す可能性のある量子効果を実装したハードウェアにアクセスしていると仮定すると、コードがN回ループして停止することなく実行される確率は1/2）** Nあなたは1 N回取得する必要があるので、任意の有限時間の間、プログラムが停止していない有限の確率が存在することを意味する。

コンピュータサイエンスサークルでより一般的に研究されている停止問題は、プログラムでは不可能な確定的なコンピュータプログラム（Turingマシンなど）の動作に関係します。たとえば、「停止問題」に関するウィキペディアの記事を参照してください。話し合い。