Share to: share facebook share twitter share wa share telegram print page

 

チューリングマシン

チューリングマシン

チューリングマシン (: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である[1]

歴史

チューリングの「計算可能数について──決定問題への応用」(1936年)において提示された[2]。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している[3]。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデル計算可能性の理論からは同等であることが確認され、チューリング=チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。

概要

ここでは非形式的(直感的)に述べる。理論的には形式的に述べる必要がある。

チューリングマシンには、いわゆるハードウェアに相当するものとして、

  1. その表面に記号を読み書きできるテープ。長さは無制限(必要になれば順番にいくらでも先にシークできる[注 1])とする
  2. テープに記号を読み書きするヘッド
  3. ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。

また、ソフトウェアに相当するものとして、以下がある。

  1. テープに読み書きされる有限個の種類の記号
  2. 最初から(初期状態において)テープにあらかじめ書かれている記号列
  3. 有限オートマトンの状態遷移規則群。詳細は次で述べる

この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」(内部状態)と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。

  • テープの「現在の場所」に新しい記号を書き込む(あるいは、現在の記号をそのままにしてもよい)
  • ヘッドを右か左に一つシークする(あるいは、移動しなくてもよい)
  • 有限オートマトンを次の状態に状態遷移させる(同じ状態に遷移してもよい)

さらに、この有限オートマトンには(一般的な有限オートマトンの「受理状態」と同様な)「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である[注 2]

現実の計算との関係

実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、アルゴリズムをチューリング機械上の手続きと同一視して議論することができる(チャーチ=チューリングのテーゼ)。

数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない(停止性問題)。これはゲーデルの不完全性定理の別の表現の形とみなすことができる。

形式的な定義

この節では、チューリングマシンを形式的(formal)に記述する。

チューリングマシン
チューリングマシン M は次の7つ組で定義される:
状態
有限集合 Q qQ状態 (state) という。
字母・記号・文字列
状態集合 Q交わらない有限集合 Γ字母alphabet)といい、字母の元 aΓ記号 (symbol) という。重複を許した有限個の記号の列全体からなる集合を Γ* と表し、その元 xΓ* を字母 Γ文字列string)またはstatement)という。
空白記号
字母 Γ のある元を空白記号 (blank) と定め、b で表す。
入力字母・入力記号
字母から空白文字を除いた Γ − {b} の部分集合 Σ入力字母input alphabet)といい、入力字母の元を入力記号input symbol)という。
遷移函数
写像 δ: Q × ΓQ × Γ × {left, right}遷移函数という。δ(q, a) = (q′, a′, m) は、「現在の状態が q であり、着目位置の記号が a であれば、状態を q′ に移し、着目位置に記号 a′ を書き込んでから、着目位置を m ∈ {left, right} 方向に1つずらす」と読む。
初期状態
状態集合 Q のある元 qinit初期状態initial state)と定める。
受理状態
状態集合 Q のある元 qacc受理状態accepting state)と定める。
状況
上の(片側)無限列のうち、状態集合 Q の元がちょうど1度現れ、また空白 b 以外の記号が有限回しか現れないものをチューリングマシン M状況configuration)という。遷移函数 δ は、状況から状況への写像を自然に定める。
受理
「チューリングマシン M が入力文字列 受理accept)する」とは、チューリングマシン M が初期状態 qinit で入力文字列 x が与えられた状況 に対し、遷移函数 δ を有限回作用させ受理状態 qacc へ遷移した状況 が得られることをいう。
実行時間・記憶領域量
チューリングマシン M が入力文字列 xΣ* を受理するまで遷移函数を作用させる最小の回数をチューリングマシン M の入力文字列 x に対する実行時間とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する記憶領域量という。

M が言語 認識するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は帰納可枚挙recursively enumerable)あるいは計算可枚挙computably enumerable)であるという。L と がともに帰納可枚挙であるとき、Lは帰納的recursive)あるいは決定可能decidable)であるという。

より精細に、自然数から自然数への写像 t に対し、M が L を時間計算量[ないし空間計算量]t で認識するとは、M が L を認識し、かつ各 に対する の実行時間[ないし記憶領域量]が 以下であることをいう。ここで は文字列 x の長さを表す。

変種

細かい相違

次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。

  • 字母の大きさ(それがを含む有限集合であるかぎり)。
  • 遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
  • 文字列を受理するさい、テープ上の記号をすべてにする必要があるか、受理状態へ移るだけでよいか。
  • テープが両方向に無限であるか、片側に終端があるか。
  • さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
  • テープの本数。

空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数からへの写像とし、状況の定義も適切に変更する。

変換機

言語を認識するだけでなく、からへの部分函数計算する機械を考えることもできる。すなわち機械は、各に対しては文字列をテープに書いてから初めて受理状態へ移り、に対しては決して受理状態へ移らない。このようなが存在するとき、部分帰納的あるいは計算可能(computable)であるという。

決定的と非決定的

遷移関数において、現在の状態 q と着目位置にある記号 a の、ある組 (q, a) に対し、値(すなわちその時にすべき動作)が、高々一つならば、そのチューリングマシンは「決定的」(deterministic)である。これに対し、動作が複数の場合は「非決定的」(non-deterministic)であり、受理の意味も再定義して、非決定的チューリングマシンや乱択チューリングマシンが定義される。また、未来と過去を逆にしても決定的であるのが可逆チューリングマシンである。

神託つき機械

質問状態を加える。

万能チューリングマシン

遷移規則をうまく構成することで、「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン(万能チューリングマシン)」が可能である。万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。(エミュレータの原理)

脚注

注釈

  1. ^ 一般的には両方向にいくらでもシークできるものとするが、理論的には片方には端があっても良いのでそのように制限することもある。
  2. ^ あるいは単に停止する場合は、停止する前に、答えがどちらであるかを、テープ上の記号列として書き残してから停止する。

出典

  1. ^ チューリングマシン」『ASCII.jpデジタル用語辞典』https://kotobank.jp/word/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3コトバンクより2022年2月2日閲覧 
  2. ^ Turing, A. M. (1937). “On Computable Numbers, with an Application to the Entscheidungsproblem” (英語). Proceedings of the London Mathematical Society s2-42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. http://doi.wiley.com/10.1112/plms/s2-42.1.230. 
  3. ^ Post, Emil L (1936). “Finite combinatory processes—formulation”. The journal of symbolic logic (Cambridge University Press) 1 (3): 103-105. doi:10.2307/2269031. https://doi.org/10.2307/2269031. Reprinted in The Undecidable, pp. 289ff.

関連項目

外部リンク

解説

  • Turing machine (英語) - スカラーペディア百科事典「チューリングマシン」の項目。
  • Turing Machines (英語) - スタンフォード哲学百科事典「チューリングマシン」の項目。
  • Weisstein, Eric W. "Turing Machine". mathworld.wolfram.com (英語).

その他

Kembali kehalaman sebelumnya


Index: pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve 
Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9