チューリングマシンについて

質問

計算理論の勉強をしています。

チューリングマシンが、ある言語を「判定する」というのと「認識する」ということの違いがよくわかりません。
どなたか解説していただけないでしょうか。

回答No.2

Budalagong · ベストアンサー

>チューリングマシンが、ある言語を「判定する」というのと
>「認識する」ということの違いがよくわかりません。

「計算理論の基礎(共立出版)」に書かれてある内容を参考にして
回答してみます。

或るチューリングマシン M が、 或る言語 L に属する文字列のみを
全て受理する場合、 「M は L を認識する」といいます。
この場合、L に属さない文字列 w を M に入力すると、M は w を
拒否して停止するか、もしくは、M は ループするかのいずれかです。　
(ループとは、決して停止状態へたどり着かない計算全般を意味します。)

また、
或るチューリングマシン M が、 或る言語 L に属する文字列のみを
全て受理し、なおかつ L に属さない文字列 w を M に入力すると、
M は 必ず w を拒否して停止する場合、「M は L を判定する」といいます。

従って、もしチューリングマシン M　が、言語 L を判定するならば、
M は L を認識します。しかし、この逆は必ずしも成り立たないです。
つまり、M が L を認識するからといって、M が L を判定するとは限らないです。

回答No.3

a-saitoh

訂正
「M が言語L を認識するとは、M が L の元のみを、かつLの元ならすべて受理することをいう。」

回答No.1

a-saitoh

同じじゃないかなぁ。
問題の文章全体を読んでみないと何とも言えませんが。勝手に判定と認識に特定の意味を与えている人が書いた文章かもしれませんし。

なお、「M が言語L を認識するとは、M が L の元のみを、かつLの元ならすべえ受理することをいう。」