王Bマシン

王浩(1954, 1957)が発表したように、彼の基本マシン Bはチューリング マシンと同等の極めて単純な計算モデルです。これは「コンピューターのようなモデルによるチューリング マシン理論の最初の定式化」です (ミンスキー、1967: 200)。4 つの連続命令のみで、ポスト チューリング マシンの 7 つの連続命令と非常に似ていますが、さらに単純です。同じ論文で、王はさまざまな同等のマシンを紹介しましたが、その中には、命令セットに「消去」命令が追加された B マシンである、彼がW マシンと呼ぶマシンも含まれています。

Wang (1954) の定義によると、B マシンが制御できる命令は 4 つだけです。

• （１）→  ：テープ走査ヘッドを１マス右へ移動（またはテープを１マス左へ移動）し、数字順に次の命令に進みます。
• （２）←  ：テープ走査ヘッドを１マス左へ移動（またはテープを１マス右へ移動）し、数字順に次の命令に進みます。
• （３）*  ：スキャンしたテープに四角いマーク*を印刷し、数字の順番で次の指示に進みます。
• (4) C n: 命令「n」への条件付き「転送」（ジャンプ、分岐）：スキャンされたテープマス目がマークされている場合は命令「n」に進み、そうでない場合は（スキャンされたマス目が空白の場合）、番号順に次の命令に進みます。

単純な B マシン命令のサンプルが彼の例です (p. 65)。

1. *、2. →、3. C2、4. →、5. ←

彼はこれを順序付きペアの集合として書き直します。

{ ( 1, * )、 ( 2, → )、 ( 3, C2 )、 ( 4, → )、 ( 5, ← ) }

ワンのWマシンは、Bマシンに命令を1つ追加しただけのものである。

• （５）E  ：スキャンしたテープマス目にある*マーク（ある場合）を消して、数字順に次の指示に進みます。

• コッドのセルオートマトン
• カウンターマシンモデル

• Hao Wang (1957)、「チューリングの計算機理論の変種」、JACM (Journal of the Association for Computing Machinery) 4; 63–92。1954 年 6 月 23 日から 25 日の協会会議で発表。
• ZA Melzak (1961) は、1961 年 5 月 15 日に「計算可能性と計算に対する非公式の算術的アプローチ」を受け取りました。Canadian Mathematical Bulletin、第 4 巻第 3 号、1961 年 9 月、279 ～ 293 ページ。Melzak は参考文献を挙げていませんが、「ベル電話研究所のR. Hamming博士、D. McIlroy 博士、V. Vyssotsky 博士、およびオックスフォード大学の H. Wang 博士との会話の恩恵」を認めています。
• Joachim Lambek (1961) は、1961 年 6 月 15 日に、Mathematical Bulletin、第 4 巻第 3 号、1961 年 9 月、295 ～ 302 ページに掲載されたHow to Program an Infinite Abacus を受理しました。付録 II で、Lambek は「プログラム」の正式な定義を提案しています。彼は Melzak (1961) と Kleene (1952)の Introduction to Metamathematicsを参照しています。
• マービン・ミンスキー(1967)、「Computation: Finite and Infinite Machines」、Prentice-Hall, Inc. Englewood Cliffs, NJ 特に、p. 262ff を参照 (原文ではイタリック体)。

「我々は、ワン[1957]によって初めて示された、あらゆるチューリングマシンTに対して、一度書き込まれた記号を決して変更しない同等のチューリングマシンT _Nが存在するという驚くべき事実を今や証明することができる。実際、我々はテープ上の空白の四角形を1に変更することしかできず、1を空白に戻すことはできない2つの記号を持つマシンT _Nを構築する。」その後、ミンスキーはこれの証明を提示する。