チューリングマシンとオートマトンでできることの違い

チューリングマシンとオートマトンでできることの違いは、具体例で言うとどういうことでしょうか？

計算理論の本を一生懸命読んでいて、数式が多くてまだ完全に理解できてないのですが、私の理解した範囲で書くと、

●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」

ですよね。

そして、ネットで調べると、「オートマトン」の例として自動販売機があって、これは非常に理解できました。
「チューリングマシン」の例としてはコンピュータがあって、これはこれで理解できました。

しかし、自動販売機にできなくてコンピュータにできること、の違いがよく分かりません。自動販売機にテープをつけると具体的にどういうメリットがあるのでしょうか？

他の例でも良いので、チューリングマシンとオートマトンでできることの違いを具体例で教えていただけると幸いです。
ぜひ、よろしくお願いいたします。

No.1 ベストアンサー 回答者： rinkun 回答日時： 2010/02/17 10:17

違いは、チューリングマシンはテープにより無制限に大きなワークエリアを取れるということでしょうか。

オートマトンの場合、
有限オートマトン：有限の状態しか取らない
プッシュダウン・オートマトン：有限オートマトン＋スタック（後入れ先出し）
線形拘束オートマトン：テープ長が入力に比例する長さに制限されている
と言ったようにワークエリアのサイズや読み書き順に強い制限があります。
# 参考: http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC% …

違いの具体例になるか分かりませんが、上記サイトには受理できる形式言語の範囲の違いが書かれていますね。

参考URL：http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC% …

この回答への補足

ありがとうございます。

やはり、このレベルになると、自動販売機、みたいな身近な例では難しいでしょうか・・・。

補足日時：2010/02/17 10:21

No.2 回答者： Tacosan 回答日時： 2010/02/17 12:39

ん～, 「チューリングマシン」はともかく, 「オートマトン」は厳密に定義しないといかんような....

たぶん, 普通の解釈では「チューリングマシンはオートマトンの一種」となると思います. すくなくとも, 「線形拘束オートマトンを『オートマトン』としておいてチューリングマシンは『オートマトンではない』とする」のは違和感がある.
また, 表現上「セルオートマトン」は「オートマトン」の一種になるはずなんだけど, これはうまく作るとチューリング完全になることが知られています. 例えば「ライフゲーム」はチューリング完全です.

この回答への補足

すみません。
オートマトンは、

有限状態オートマトン

を意図して書きました。

質問は、有限状態オートマトンとチューリングマシンにできることを身近な例で理解できないか、ということでした。（自動販売機、というのは分かり易いのですが・・・、やはり、チューリングマシンとの比較を考えると言語の受理じゃないと適切な具体例ないでしょうか・・・）

補足日時：2010/02/17 15:43

この回答へのお礼

なお、私の書いた

●「チューリングマシン」 ＝ 「オートマトン」 ＋ 「テープ（記憶）」

は http://www.infonet.co.jp/ueyama/ip/history/turin … に書いてある

「チューリングマシンは無限に長いテープと、 テープに書かれている記号を読みとって内部の状態を変える自動機械 （オートマトン） からなっています。 」

も参考にしました。

お礼日時：2010/02/17 18:12