状態遷移図とチューリングマシンとは

質問

アルゴリズムについて学んでいた際、
「状態遷移図」と「チューリングマシン」という言葉が出てきました。
この二つはどういう関係と意味を持っているのでしょうか？
調べてみたのですがオートマトンやら難しい計算式ばかり出てきてあまり理解できませんでした。

計算式を見て理解できないならそれまでなのかもしれませんが、
何か比較的簡単な説明を頂けないでしょうか？
お願いします。

回答No.2

anmochi · ベストアンサー

状態遷移図とは文字通り状態が遷移していく様を表したもので、これはそのまま今から考えようとしている対象が状態を持っている事を意味している。状態遷移でよく例として出る自動販売機（Vending Machines）を考えてみよう。

　この自動販売機には商品が4つあり、それぞれ10円、50円、120円、200円だ。この値段は状態ではない（より複雑なモデルでは状態である場合もある）。状態は、4つの商品それぞれの在庫数と、現在投入されている金額だ。さらに、4つの商品用のボタンは押せる時には光る事にしよう。そうするとボタンが光っているかそうでないかも状態であらわされる事になる。
　仮にそれぞれ在庫数が5つであり、現在の投入金額は0円であるという状態になっていたとする。投入金額は0円であるので当然ボタンは4つとも光っていない。

　ここでお客さんが100円玉を一枚投入した（トリガー）。すると、投入金額は0円から100円へと変化する。さらに、価格が10円の商品と50円の商品のボタンが押せる状態（光る状態）に変化する。120円と200円のボタンは光らないまま（変化しない）だ。
　さらに、お客さんが50円の商品のボタンを押す（トリガー）と、商品が取り出し口へ送られ、投入金額が100円から50円へ変化し、50円の商品の在庫数が5から4へ変化し、・・・・。
　という風に、「自動販売機」をプログラムあるいは概念としてモデリングすると、それは状態を持つプログラムになり、同じ動作（トリガー）を行ったとしても状態によって反応が変わる。そして、同じ状態で同じトリガーが発生すると必ず同じ結果をもたらす。これを決定性有限オートマトンという。自動販売機（の概念）は典型的な決定性有限オートマトンと言えよう。
　アルゴリズムの勉強であれば電卓をモデリングしてみると状態と状態遷移を絡めたアルゴリズムについて理解できるであろう。電卓は、例えば4のボタンが押された時、直前に押されたボタンが3だった場合は現在表示中の数字の後ろに4が加わり、直前に押されたボタンが＋だった場合は現在表示中の数字がクリアされ4だけが表示される状態に変わる。なかなかモデリングしがいのあるモデルだ。

　チューリングマシンというのは、超適当に言うと、メモリを持ち、ハードディスクは持たず、入力装置がキーボードではなく磁気テープであるようなパソコンをイメージすれば良い。これもメモリの内容が状態であり、磁気テープがトリガーであるオートマトンと言える。

　う～ん、最も簡単な説明にしたつもりだが、どうだろう。
　ところで、この説明では遷移と変化は意図的に使い分けている。自動販売機であれば、投入金額、在庫数、ボタンの点灯それぞれが単独で変わるのを変化と言い、全体として自動販売機の状態がどう変わったかを遷移と言っている。例えば、100円を入れると投入金額が100円増えることを変化と言い、結果として、投入金額0円、在庫数はすべて5、ボタンはすべて光っていないという状態から、投入金額100円、在庫数はすべて5、ボタンは10円と50円のものが光っていて120円と200円のものは光っていないという状態へ遷移したと表現している。これは「状態」は静的であるという考えに基づくものなのでそういうものなのかと思いながら読み飛ばしていただけたらと思う。

お礼

とても詳しい説明本当にありがとうございました。
内容については十分理解できました。

回答No.3

dscripty

それ系の大学ならそれの講義があるはずだから、
調べて、聴講するか、
それ系の講義で使うような教科書的な参考書を読むか、
かな？

「チューリングマシン」とか「オートマトン」とかは
ざっくりいっちゃうと、

コンピュータが
機能上
どんな限界(制限？)を持っているか？

の単なる区分だから、コンピュータの「種(分類学)」
→http://ja.wikipedia.org/wiki/%E7%A8%AE_%28%E5%88%86%E9%A1%9E%E5%AD%A6%29
ぐらいの理解でいいとおもうよ？

アルゴリズムだけの学習なら必ず必要ってわけじゃないし、
いまは、とりあえず、読み飛ばしちゃおう！

状態遷移は [ANo.2] さんの回答を見てね。

回答No.1

root139

かなり大雑把な表現ですが、入力などに使う文字(アルファベット)が既に与えられているとして、

・状態遷移図のみで表現する事が出来るのが有限オートマトン(正規表現)
・状態遷移図＋スタックで表現する事が出来るのがプッシュダウンオートマトン(文脈自由文法)
・状態遷移図＋無限長の読書き可能なテープで表現する事が出来るのがチューリングマシン

という感じでしょうか。