本稿では，sasanqua_neufのチューリング完全性を証明します．具体的には，チューリングマシンのエミュレータを構成することでチューリング完全性を示します． 概要 sasanqua_neufのテープTをチューリングマシンのテープと「概ね」同一視し，チューリングマシンの状態をCの値によって「概ね」表現します．C言語風にエミュレータの概要を記すと，全体の構造としては int Cq=1; while(Cq != n+1){ switch(Cq){ case 1: //qの添え字が1 switch(T[H]){ //T[H]にσが格納されている case 1: //σの添え字が1 T[H] = [δ_2(q_1,σ_1)]; //T[H]をテープと同一視 H += [δ_3(q_1,σ_1)]; //ただしLeft=-1,Right=+1と見て while(T[H] == 0){getchar
Difference Engineは機械式の加算機であったが、より一般的に、機械的な計算手順でどのような問題が解きうるのかという研究がなされ、1936年に、Alan Turing氏は、計算する機械のモデルとして次のような概念的な機構を考えた。 無限に長いテープがあり、それに書かれたデータを読んだり、新しい値を書き込んだりするヘッドがある。そして、ヘッドから読まれた"1/0"に応じて状態遷移を行う有限のステートマシン(現在の状態とヘッドからの入力の"1/0"に応じて次の状態が定義されており、状態の数が有限の回路)があり、その状態に応じて、ヘッドを1ビット分、右や左に動かし、データを読んだり書いたりする。そして、最終状態と定義した状態に辿り着いたら、問題に対する答えがテープ上に書かれているという機械である。 Stanford Encyclopedia of Philosophyに書かれている足
Computing Machinery and Intelligence 計算する機械と知性 A. M. Turing アラン M. チューリング back Originally published by Oxford University Press on behalf of MIND (the Journal of the Mind Association), vol. LIX, no. 236, pp. 433-60, 1950. Acknowledge original place of publication and by permission of Oxford University Press or the sponsoring society if this is a society journal. 利用条件: 個人 web サイトのみ。個人的な研究目的のために 1部のみ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く