- ベストアンサー
状態遷移図とチューリングマシンとは
アルゴリズムについて学んでいた際、 「状態遷移図」と「チューリングマシン」という言葉が出てきました。 この二つはどういう関係と意味を持っているのでしょうか？ 調べてみたのですがオートマトンやら難しい計算式ばかり出てきてあまり理解できませんでした。 計算式を見て理解できないならそれまでなのかもしれませんが、 何か比較的簡単な説明を頂けないでしょうか？ お願いします。
- その他([技術者向] コンピューター)
- 回答数3
- ありがとう数1
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
状態遷移図とは文字通り状態が遷移していく様を表したもので、これはそのまま今から考えようとしている対象が状態を持っている事を意味している。状態遷移でよく例として出る自動販売機（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円のものは光っていないという状態へ遷移したと表現している。これは「状態」は静的であるという考えに基づくものなのでそういうものなのかと思いながら読み飛ばしていただけたらと思う。
その他の回答 (2)
- dscripty
- ベストアンサー率51% (166/325)
それ系の大学ならそれの講義があるはずだから、 調べて、聴講するか、 それ系の講義で使うような教科書的な参考書を読むか、 かな？ 「チューリングマシン」とか「オートマトン」とかは ざっくりいっちゃうと、 コンピュータが 機能上 どんな限界(制限？)を持っているか？ の単なる区分だから、コンピュータの「種(分類学)」 →http://ja.wikipedia.org/wiki/%E7%A8%AE_%28%E5%88%86%E9%A1%9E%E5%AD%A6%29 ぐらいの理解でいいとおもうよ？ アルゴリズムだけの学習なら必ず必要ってわけじゃないし、 いまは、とりあえず、読み飛ばしちゃおう！ 状態遷移は [ANo.2] さんの回答を見てね。
- root139
- ベストアンサー率60% (488/809)
かなり大雑把な表現ですが、入力などに使う文字(アルファベット)が既に与えられているとして、 ・状態遷移図のみで表現する事が出来るのが有限オートマトン(正規表現) ・状態遷移図＋スタックで表現する事が出来るのがプッシュダウンオートマトン(文脈自由文法) ・状態遷移図＋無限長の読書き可能なテープで表現する事が出来るのがチューリングマシン という感じでしょうか。
関連するQ&A
- チューリングマシンとオートマトンでできることの違い
チューリングマシンとオートマトンでできることの違いは、具体例で言うとどういうことでしょうか？ 計算理論の本を一生懸命読んでいて、数式が多くてまだ完全に理解できてないのですが、私の理解した範囲で書くと、 ●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」 ですよね。 そして、ネットで調べると、「オートマトン」の例として自動販売機があって、これは非常に理解できました。 「チューリングマシン」の例としてはコンピュータがあって、これはこれで理解できました。 しかし、自動販売機にできなくてコンピュータにできること、の違いがよく分かりません。自動販売機にテープをつけると具体的にどういうメリットがあるのでしょうか？ 他の例でも良いので、チューリングマシンとオートマトンでできることの違いを具体例で教えていただけると幸いです。 ぜひ、よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- チューリング機械の状態遷移図
h(x)=0(x=0のとき),定義されない(x>0のとき) のチューリング機械の状態遷移図を書け という問題なのですが、x>0のときというのが難しいです。 チューリング機械ではx≠0ということは指定できないですよね？ こういった場合はどのように書けばいいのでしょうか？ あと、「定義されない」ということなんですが最終的に空白なマスにとどまっていればいいのでしょうか？
- ベストアンサー
- 数学・算数
- チューリングマシンの状態数について
この質問で言うチューリングマシンは、 「使用できる文字が0,1,Xだけのもの」とします。 自然数nに対し、 「空列を入力して動作を開始すると、有限ステップで停止して、停止したときにテープに書き残されている文字数がn以上」 であるようなチューリングマシンを全て集めた集合をKnとします。 そして、 g(n)= min{size(M) | M∈Kn } とします。ただし、size(M)はチューリングマシンMの状態数であり、minは「最小値」を意味します。 各nに対してKnは非空集合なので、g(n)の値はどんなnに対しても一意に定義されます。 すなわち、gは自然数上の全域関数です。 ビジービーバー関数は「状態数」から「その状態数のチューリングマシンが書き残せる最大字数」を求めるものでありますが、 この関数gは「字数」から「それ以上の字数を書き残せるチューリングマシンの最小状態数」を求めるものです。 このgが計算可能であるか、計算不可能であるかを述べて、そのことを証明してください。 よろしくお願いいたします。 ((関数が)計算可能の定義は、「それを計算するＣ言語プログラムが存在する」です。)
- ベストアンサー
- C・C++・C#
- チューリングマシン
チューリングマシン 現在の状態 0 0 0 0 1 1 1 読んだ文字 0 1 X □ 0 0 1 ーーーーーーーーーーーーーーーー...以下略 次の状態 1 2 0 終 1 3 1 書く文字 □ □ □ □ ０ X X 移動方向 右 右 右 右 左 右 「０」「１」が連続して書かれていて、調べたい０，１の前後は□になっています。 左から一文字ずつ消していき、その際左端が０なら１を、１なら０を1つ消す。 このチューリングマシンは、このようにして「０」「１」の数がちょうど等しいかどうかを調べるものらしいのですが、どうして次の状態に２，３がでてくるのか?また、なぜ左に戻ったりするのか？などいまいちよくわかりません。 詳しく載っているサイトか、説明をお願いします。
- 締切済み
- 数学・算数
- この表と図の意味を詳しく教えてください
この画像にある「状態遷移表」「状態遷移図」が何故こうなるのか理解できません。詳しく説明してもらえませんか。
- ベストアンサー
- その他([技術者向] コンピューター)
- 遷移状態が生じる理由？
量子化学の内容です。等核二原子分子が解離する反応(A2→2A)では遷移状態はないですよね。でも等核二原子分子が解離する際に他の原子と反応する反応(A2+B→A+AB)では、遷移状態があるらしいのです。 これは教科書に載っていたことなのですが、なぜ後者の反応で遷移状態が生じるかという理由までは載っていませんでした。縦軸にポテンシャルエネルギー、横軸に核間距離をとったグラフが関係あると思うのですが、詳しいところはよく分かりません。 分かる方教えてください。よろしくお願いします。
- ベストアンサー
- 化学
- 無限状態オートマトンの説明
教科書の以下の説明が1週間ぐらい何度も試みたのですが理解できません。 無限状態オートマトンとしては入力wに関する情報として系列wそのものを 状態qwとして覚えるものと考え、状態遷移関数をw∈Σ*,a∈Σにたいして δ(qw,a)=qwaと定義する。 開始状態をqεとし、受理状態の集合として、F={qw|w∈L}と指定する。 このように指定したオートマトンにw=a1a2・・・anを入力すると、 qε→qa1→qa1a2→・・・→qa1・・・anと遷移し、w∈Lのとき、qwは受理状態 であるのでwは受理される。 宜しくお願いします。
- ベストアンサー
- 数学・算数
- スレッドの状態遷移について。。。
Javaの本を買って読んでいます。 その中の「スレッド」のカテゴリーの「状態遷移」のところの「synchronized」の部分に、こう書かれています。 -------------------------- ・・・・・・ なお、sleepメソッドでスリープ状態（実行不可能状態）になったスレッドはロックを保持したまま開放しません。 そのため、ロックを取得できないで待たされるスレッドも実行不可能状態へ移行させられます。 -------------------------- これは、Synchronized指定されたメソッド（同期メソッド）の部分で出てきた文章でして、 私は、こう解釈しました。 → 例えば、同じオブジェクトの参照を引数とするスレッドが３つあり、その中の１つが『実行中』状態にある（仮に t１ とする）として（つまり残り２つ（ t２ t３ ）は『実行可能状態（プール）』にある。）、 実行中の t１ がsleep()メソッドで『実行不可能状態』になった場合、 『実行可能状態』にあった、t２ t３ も『実行不可能状態』へ移行する事になる。 間違っていますか？ もし、この解釈が正しければ、こうなりますよね？ t１・・・・・・・『実行中』 → 『実行不可能状態』 t２ t３・・・『実行可能状態』 → 『実行不可能状態』 ところが、状態遷移の５つの状態の図を見ると、 『実行可能状態』 から 『実行不可能状態』 へは、矢印→が書かれておりません。（逆向きの矢印がありますが。） どういう意味でしょうか。 java初心者ですが、 解りやすく教えて頂けると助かります。 宜しくお願い致します。
- ベストアンサー
- Java
- オートマトンについて（３）
以下の問題も解けず困っています。よろしくお願いします。 以下の言語を受理するオートマトンを設計せよ。 L＝｛w|wは０と１からなる文字列で、どこかに100がある｝ 例えば10010∈Lである。 オートマトンは状態遷移図でも形式的表現でもよい。 オートマトンについても詳細を加えていただくとありがたいです。 よろしくお願いします。
- 締切済み
- 数学・算数
お礼
とても詳しい説明本当にありがとうございました。 内容については十分理解できました。