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

質問

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

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

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

ですよね。

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

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

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

回答No.1

rinkun · ベストアンサー

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

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

参考URL：

http://ja.wikipedia.org/wiki/%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3

補足

ありがとうございます。

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

回答No.2

Tacosan

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

お礼

なお、私の書いた

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

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

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

も参考にしました。

補足

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

有限状態オートマトン

を意図して書きました。

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