0

Math exchange から次の説明を見つけました

その言語の文字列のみを停止して受け入れるチューリング マシンが存在する場合、その言語は認識可能であり、その言語にない文字列の場合、TM は拒否するか、まったく停止しません。注: チューリング マシンが言語に含まれていない文字列に対して停止する必要はありません。

その言語に含まれる文字列を受け入れ、その言語に含まれない文字列を拒否するチューリング マシンが存在する場合、その言語は決定可能です。」

2つの違いがよくわかりません。ある言語の文字列のみを受け入れるチューリング マシンと、ある言語の文字列を受け入れるチューリング マシンの違いは何ですか? チューリングマシンは何でも受け入れることができるということですか?

4

2 に答える 2

0

違いは、ディサイダー (決定する TM) は常に任意の入力 (受け入れるか拒否するかに関係なく) で停止するのに対し、レコグナイザーは停止以外に永遠にループする可能性があることです。永遠にループする場合、認識エンジンは「永久に」数回経過した後にのみ決定できます。決定できない場合があるため、決定者ではなく認識者と呼ぶのはそのためです。

于 2015-03-26T06:04:37.080 に答える