チューリングマシン

2014-01-08T01:22:54Z

163.136.21.137: /* 決定的と非決定的 */

{{出典の明記|date=2011年12月}}
'''チューリングマシン '''({{lang-en-short|''Turing Machine''}}) は[[計算模型]]のひとつで、[[計算機]]を[[数学]]的に[[議論]]するための単純化・[[理想]]化された[[仮想機械]]である。

== 歴史 ==
[[1936年]]に[[イギリス]]の数学者[[アラン・チューリング]]の論文「計算可能数について──[[決定問題]]への応用」で発表された。同様の考え方は同年に[[エミール・ポスト]] (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。

== 概要 ==
[[Image:Turing Machine.png|right|300px|thumb|'''チューリングマシンの模式図''' 無限に長い節からできたテープと、テープの節を読み書きするヘッドから構成されている。ヘッドは読み取った節の内容を記憶できる。]]
チューリングの仮想機械は、
#無限に長いテープ
#その中に格納された情報を読み書きするヘッド
#機械の内部状態を記憶するメモリ
で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。
*ヘッド位置のテープに情報を書き込む
*機械の内部状態を変える
*ヘッドを右か左に一つ移動する
上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。

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

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

== 形式的定義 ==
チューリング機械とは次の<math>7</math>つ組<math>M = \langle Q, \mathit\Gamma, b, \mathit\Sigma, \delta, q _{\mathrm{init}}, q _{\mathrm{acc}} \rangle</math>である。
* Q は[[有限集合]]であり、その元を'''状態'''という。
* ''Γ'' は ''Q'' に交わらない有限集合であり、'''[[アルファベット (計算機科学)|字母]]'''とよばれる。その元を'''記号'''という。
* b は ''Γ'' の元であり、'''空白記号'''とよばれる。
* ''Σ'' は ''Γ'' - {b} の部分集合であり、'''入力字母'''とよばれる。その元を'''入力記号'''という。
* δ は Q × ''Γ'' から Q × ''Γ'' × {left, right} への写像であり、'''遷移函数'''とよばれる。δ(q, a) = (q', a', m) は、「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
* q<sub>init</sub> は Q の元であり、'''初期状態'''とよばれる。
* q<sub>acc</sub> は Q の元であり、'''受理状態'''とよばれる。
M の'''状況'''とは、<math>\mathit\Gamma \cup Q</math>上の（片側）無限列のうち、Q の元がちょうど1度現れ、また b 以外の記号が有限回しか現れないものをいう。遷移函数 δ は、状況から状況への写像を自然に定める。M が文字列<math>x \in \Sigma ^*</math>を'''受理'''するとは、状況<math>q _{\mathrm{init}} x b b \cdots</math>にこの写像を有限回施すことで状況<math>q _{\mathrm{acc}} b b \cdots</math>が得られることをいう。その最小回数を M の x に対する'''実行時間'''とよぶ。その過程における状況中の q の最右位置を、M が x に対して使用する'''記憶領域量'''という。

M が言語<math>L \subseteq \mathit\Sigma ^*</math>を'''認識'''するとは、M が L の元のみをみな受理することをいう。そのようなチューリング機械 M が存在するとき、L は'''帰納可枚挙'''（recursively enumerable）あるいは'''計算可枚挙'''（computably enumerable）であるという。L と<math>\mathit\Sigma ^* \setminus L</math>がともに帰納可枚挙であるとき、Lは'''帰納的'''（recursive）あるいは'''決定可能'''（decidable）であるという。

より精細に、自然数から自然数への写像 t に対し、M が L を'''時間計算量'''［ないし'''空間計算量'''］t で認識するとは、M が L を認識し、かつ各<math>x \in L</math>に対する<math>M</math>の実行時間［ないし記憶領域量］が<math>t (\left| x \right|)</math>以下であることをいう。ここで<math>\left| x \right|</math>は文字列 x の長さを表す。

== 変種 ==
=== 細かい相違 ===
次の各項目について上記の定義に変更を施しても、帰納可枚挙な言語は変わらず、また時間計算量や空間計算量に対する影響も小さい。このため、チューリング機械の定義の詳細は文献によって異なっている。
* 字母<math>\mathit\Gamma</math>の大きさ（それが<math>\mathit\Sigma</math>を含む有限集合であるかぎり）。
* 遷移函数が着目位置を左右に必ず動かすか、同じ位置に留まる事を許すか。
* 文字列を受理するさい、テープ上の記号をすべて<math>b</math>にする必要があるか、受理状態へ移るだけでよいか。
* テープが両方向に無限であるか、片側に終端があるか。
* さらに、記憶領域が一次元のテープであるか、より複雑な形状をしているか。
* テープの本数。
空間計算量を細かく調べるときには、書き換えできない入力専用テープを設けて、そこでの使用領域量を無視することがある。すなわち、遷移函数<math>\delta</math>を<math>Q \times \mathit\Gamma ^2</math>から<math>Q \times \mathit\Gamma \times \{\mathrm{left}, \mathrm{right}\} ^2</math>への写像とし、状況の定義も適切に変更する。

=== 変換機 ===
言語を認識するだけでなく、<math>\mathit\Sigma ^*</math>から<math>\mathit\Sigma ^*</math>への部分函数<math>f</math>を'''計算'''する機械を考えることもできる。すなわち機械<math>M</math>は、各<math>x \in \mathrm{dom} (f)</math>に対しては文字列<math>f (x)</math>をテープに書いてから初めて受理状態へ移り、<math>x \notin \mathrm{dom} (f)</math>に対しては決して受理状態へ移らない。このような<math>M</math>が存在するとき、<math>f</math>は'''部分帰納的'''あるいは'''[[計算可能性理論|計算可能]]'''（computable）であるという。

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

=== 神託つき機械 ===
{{main|神託機械}}
質問状態を加える。

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


==関連項目==
{{commons|Category:Turing machine}}
{{Refbegin|2}}
* [[チューリング完全]]
* [[非決定性チューリングマシン]]
* [[コルモゴロフ複雑性]]
* [[ライフゲーム]]
* [[停止性問題]]
* [[可逆チューリングマシン]]
* [[オートマトン]]
{{refend}}

== 外部リンク ==
=== 解説 ===
* {{Spedia|Turing_machine|Turing machine}}
{{SEP|turing-machine/|Turing Machines}}
* {{MathWorld|urlname=TuringMachine|title=Turing Machine}}

=== その他 ===
* [http://wired.jp/wv/2007/10/26/%e3%80%8c%e3%82%a6%e3%83%ab%e3%83%95%e3%83%a9%e3%83%a0%e6%b0%8f%e3%81%ae%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%e3%80%8d%e3%82%9220%e6%ad%b3%e3%81%ae%e5%ad%a6/ 「ウルフラム氏のチューリングマシン」を20歳の学生が証明]

{{DEFAULTSORT:ちゆうりんくましん}}
[[Category:理論計算機科学]]
[[Category:計算モデル]]
[[Category:形式手法]]
[[Category:数学に関する記事]]
{{Computer-stub}}

岩崎正洋

2013-05-14T02:34:51Z

163.136.21.137:

{{BLP unsourced|date=2012年9月20日 (木) 03:21 (UTC)}}
'''岩崎正洋'''（いわさきまさひろ、[[1965年]] - ）は、[[日本]]の[[政治学者]]。

[[静岡県]][[清水市]]（現[[静岡市]]清水区）生まれ。[[東海大学第一高等学校]]、[[東海大学]]政治経済学部卒業。同大学大学院政治学研究科修了。博士（政治学）。東海大学政治経済学部[[助手 (教育)|助手]]、[[杏林大学]][[総合政策学部]][[助教授]]を経て、2006年4月、日本大学法学部助教授。同[[准教授]]を経て、現在[[日本大学]][[法学部]][[教授]]。

==著書==
===単著===
*『政党システムの理論』（[[学校法人東海大学出版会|東海大学出版会]], 1999年）
*『議会制民主主義の行方』（一藝社, 2002年）
*『電子投票』（[[日本経済評論社]], 2004年）
*『政治発展と民主化の比較政治学』（東海大学出版会, 2006年）
*『eデモクラシーと電子投票』（日本経済評論社, 2009年）

===編著===
*『サイバーポリティクス――IT社会の政治学』（[[一藝社]], 2001年）
*『かわりゆく国家』（一藝社, 2002年）
*『eデモクラシーと行政・議会・NPO』（一藝社, 2004年）
*『ガバナンスの課題』（東海大学出版会, 2005年）
*『eデモクラシー』（日本経済評論社, 2005年）
*『政党システムの理論と実際』（おうふう, 2011年）
*『ガバナンス論の現在』（勁草書房, 2011年）

===共編著===
*（[[青木一能]]・[[野口忠彦]]）『比較政治学の視座』（新評論, 1998年）
*（[[工藤裕子]]・[[佐川泰弘]]・B・サンジャック, J・ラポンス）『民主主義の国際比較』（一藝社, 2000年）
*（[[植村秀樹]]・[[宮脇昇]]）『グローバリゼーションの現在』（一藝社, 2000年）
*（[[河野勝]]）『アクセス比較政治学』（日本経済評論社, 2002年）
*（佐川泰弘・[[田中信弘]]）『政策とガバナンス』（東海大学出版会, 2003年）
*（佐川泰弘）『ファ－ストステップ日本の政治』（一藝社, 2003年）
*（[[岸川毅]]）『アクセス地域研究(1)民主化の多様な姿』（日本経済評論社, 2004年）
*（[[小川有美]]）『アクセス地域研究(2)先進デモクラシーの再構築』（日本経済評論社, 2004年）
*（[[河野武司]]）『利益誘導政治――国際比較とメカニズム』（芦書房, 2004年）
*（[[河井孝仁]]・[[田中幹也]]）『コミュニティ』（日本経済評論社, 2005年）
*（[[田中信弘]]）『公私領域のガバナンス』（東海大学出版会, 2006年）
*（[[坪内淳]]）『政治のレシピ――「旬の素材」で読むニッポン事情』（メタブレーン, 2006年）
*（坪内淳）『政治学の現在シリーズ (1)国家の現在』（芦書房, 2007年）
*（[[西岡晋]]・[[山本達也]]）『政治の見方』（八千代出版,2010年）
*（秋山和宏）『国家をめぐるガバナンス論の現在』(勁草書房,2012年)

===訳書===
* H・E・アレキサンダー, [[白鳥令]]編『民主主義のコスト――政治資金の国際比較』（[[新評論]], 1995年）

{{デフォルトソート:いわさきまさひろ}}
[[Category:日本の政治学者]]
[[Category:日本大学の教員]]
[[Category:杏林大学の教員]]
[[Category:静岡市出身の人物]]
[[Category:1965年生]]
[[Category:存命人物]]

Wikippe - 利用者の投稿記録 [ja]

チューリングマシン

岩崎正洋