2017-01-01から1ヶ月間の記事一覧

Wolfram's (2, 3)-Turing machineの「普遍性の証明」を読む

ここで,(2, 3)-Turing machineとはstateが2つ,テープalphabetsが3つのTuring machineのこと。alphabetsを{0, 1, 2}とおき,statesを{A, B}とおく。Wolframが次の遷移規則の(2, 3)-Turing machineが普遍 (universal) か否かに懸賞金25,000 USDをかけた。 A …