ゼノン機械と計算可能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/20 05:31 UTC 版)
「ゼノン機械」の記事における「ゼノン機械と計算可能性」の解説
ゼノン機械はチューリング計算可能でないような或る関数の計算を可能にする。例えばチューリング機械の停止問題はゼノン機械によって解ける（以下の擬似コードアルゴリズムを用いる）。 入力：チューリング機械 T {\displaystyle T} 、文字列 w {\displaystyle w} 出力テープの初期位置に 0 {\displaystyle 0} を印字する; begin loop T ( w ) {\displaystyle T(w)} の計算を一段階だけシミュレートする もし T ( w ) {\displaystyle T(w)} の計算がこのステップで完了したなら、出力テープの初期位置に 1 {\displaystyle 1} を印字し、ループを抜ける end loop このプログラムはゼノン機械によって一単位時間で実行される。計算が終了した時点で出力テープには停止問題の正しい解が印字される。 この種のチューリング限界の彼方にある計算はハイパーコンピュテーション（このケースのものはスーパータスクによるハイパーコンピュテーション）と呼ばれる。さらなる議論と文献については当該記事を参照。
※この「ゼノン機械と計算可能性」の解説は、「ゼノン機械」の解説の一部です。
「ゼノン機械と計算可能性」を含む「ゼノン機械」の記事については、「ゼノン機械」の概要を参照ください。
ウィキペディア小見出し辞書の「ゼノン機械と計算可能性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ゼノン機械と計算可能性のページへのリンク
