ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻み
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/02 05:58 UTC 版)
「レジスタマシン」の記事における「ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻み」の解説
そこで、テープを無限長（任意の整数を格納できる）の断片に分けるという考え方が出てくる。それぞれにヘッドがあり、デクリメントでは左に移動し、インクリメントでは右に移動する。ある意味で、ヘッドの位置がマークのスタックの先端を指す。ミンスキー (1961) および Hopcroft and Ullman (1979, p. 171ff) では、テープは左端から続くマーク部分以外は常に空白状態とされた（ヘッドがそこまで移動したことがない場合でも）。つまり、記録されたマークの個数が整数値に対応する。このモデルでは、デクリメントする前にゼロかどうかを確認しないと、テープの端をつき抜けてしまう。 ミンスキー (1961) と Shpepherdson-Sturgis (1963) は、テープが1つであっても、このモデルがチューリング等価であることを示した。この場合、テープ上のデータはゲーデル数（あるいは何らかの一意に符号化/複号化可能な数）とされる。この数は計算の進行に伴って変化する。ゲーデル数の符号化を伴う1つのテープのバージョンでは、カウンタマシンは (1) ゲーデル数に定数（2とか3）をかける操作ができ、(2) 定数（2や3）で割って、余りがゼロなら分岐する操作ができる必要があるとされた。ミンスキー (1967) では、これらの奇妙な命令の代わりに { INC (r), JZDEC (r, z) } で十分とされ、さらにテープ（すなわちレジスタ）が2つあれば { CLR (r), J (r) } で等価となることが示された。ただし、単純なゲーデル数化は依然として必要である。RASP モデルについての同様の研究は Elgot-Robinson (1964) でなされている。
※この「ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻み」の解説は、「レジスタマシン」の解説の一部です。
「ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻み」を含む「レジスタマシン」の記事については、「レジスタマシン」の概要を参照ください。
- ミンスキー、Melzak-Lambek、Shepherdson-Sturgis モデルによるテープの切り刻みのページへのリンク
