無限実行

ウィキペディア小見出し辞書

無限実行

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/17 08:19 UTC 版)

「計算可能性理論」の記事における「無限実行」の解説

計算の各ステップが前のステップの半分の時間しかかからない機械を考える。第一ステップにかかる時間を 1 に正規化すると、実行にかかる時間は 1 + 1 2 + 1 4 + ⋯ となる。この無限数列の総和は 2 に近づいていく。つまり、このチューリングマシンは 2 単位の時間内に無限の処理を実行できる。この機械は、対象となる機械の実行を直接シミュレーションすることで停止問題の判定が可能である。