レジスタマシンモデルの歴史的発展
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/02 05:58 UTC 版)
「レジスタマシン」の記事における「レジスタマシンモデルの歴史的発展」の解説
1950年代初期に2つの方向性が現れた。第一はコンピュータをチューリングマシンとしてモデリングする方向で、第二はチューリングマシンと同等の能力がある、よりコンピュータ的モデル（つまり、逐次命令実行と条件付き命令のあるモデル）を定義する方向である。これらの研究は2つの難しい問題の解を得る努力の過程でなされた。ひとつはエミール・ポストの提示した未解決問題（タグ問題）、もうひとつはヒルベルトの23の問題の10番目のディオファントス方程式にまつわる問題である。研究者らは、「論理」性がより少なく、「算術」性が強いチューリング等価なモデルを捜し求めていた。(cf Melzak (1961) p. 281, Shepherdson-Sturgis (1963) p. 218)。 第一の方向性は、Hans Hermes (1954) や Heinz Kaphengst (1959) が創始し、第二の方向性は Hao Wang (1954, 1957) が創始し、上述のように Z. A. Melzak (1961)、Joachim Lambek (1961)、マービン・ミンスキー (1961, 1967)、John Shepherdson と H. E. Sturgis (1963) が後に続いた。 後者の名前を挙げた順序は、ユーリ・マチャセビッチがリストアップした順序である。彼は、次のように述べている。 「レジスタマシンは特にディオファントス方程式の構築に適している。チューリングマシンのように、それらは非常に基本的な命令しか持たず、さらに数を扱う」(Yuri Matiyasevich (1993), Hilbert's Tenth Problem, commentary to Chapter 5 of the book, at http://logic.pdmi.ras.ru/~yumat/H10Pbook/commch_5.htm ) Lambek、Melzak、ミンスキー、Shepherdson、Sturgis らは、ほぼ同時期に同じ考え方に到達した。 歴史は、Wang のモデルから始まる。
※この「レジスタマシンモデルの歴史的発展」の解説は、「レジスタマシン」の解説の一部です。
「レジスタマシンモデルの歴史的発展」を含む「レジスタマシン」の記事については、「レジスタマシン」の概要を参照ください。
- レジスタマシンモデルの歴史的発展のページへのリンク
