ペンローズ『皇帝の新しい心』の万能テューリング機械


皇帝の新しい心―コンピュータ・心・物理法則ペンローズ『皇帝の新しい心』(みすず書房, 1994)

ユニバーサル・チューリング・マシンのMathematicaによる実装

この1654桁の10進数が万能テューリングマシンとして動く様子がわかるUniversal Mathematica Manipulator (UMM)でも動作する)

状態遷移図は下の通り(状態数201)。

万能チューリングマシンの状態遷移図

クイズ ペンローズによるテューリング機械の記述を解釈できるような万能テューリング機械tmに、テューリング機械Aの記述aとAへの入力bを与える。aがuだとするとAは万能テューリング機械になる。Aが万能テューリング機械ならば、Aへの入力(つまりb)はテューリング機械Cの記述cとCへの入力dからなる。cがuだとするとCは万能テューリング機械になる。Cが万能テューリング機械ならば、Cへの入力(つまりd)はテューリング機械Eの記述eとEへの入力fからなる。EがUN+1でfが{1}であるように全体を構成することはできるだろうか?

つまり、以下は可能か?

  1. コンピュータで万能テューリング機械tmをシミュレートする
  2. tmで万能テューリング機械Aをシミュレートする
  3. Aで万能テューリング機械Cをシミュレートする
  4. Cで足し算をするテューリング機械UN+1をシミュレートする
  5. UN+1で1+1を計算する

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です