私は私が確信していた問題に出くわしました。好奇心のために、私は質問したかった：チューリングマシンは、チューリングマシンが処理できない文字列を停止し、暗黙的に受け入れることができますか？
チューリングマシンは暗黙のうちに扱えない文字列を拒否できますが、その補完はできますか？言い換えれば、それは暗黙のうちにを受け入れることができないのですか？これが愚かな質問であれば、私はお詫びします。私はこれに対する答えを見つけることができません。
これは愚かな質問ではありません！私は、「扱えない文字列」は、実際には「有効な形式ではない文字列」という意味で、「わからない記号を含む文字列」を意味すると考えています。 （私はちょうどTuring 'implicitly reject'をグーグルで見つけたthis presentationのスライド14から出ます）。
その定義を使用すると、有効なセットにないシンボルが含まれている場合は、入力を受け入れるチューリングマシンを作成するだけで済みます。
はい、「扱うことができない文字列」の解釈がありますが、これはこれを意味すると私は確信しています。当然のことながら、制約のない定義であることはできませんでした。そうでなければ、「処理できない文字列」を「停止するプログラムを表す文字列」として定義でき、停止問題を解決できました。 （あるいは、停止問題に慣れていない場合は、本当にNP完全な問題に置き換えることができます）。
私はチューリングマシンが扱えない文字列を拒否するという考えは、最初に導入された理由は、マシンがすべての入力に対してうまく定義できることだと思います。たとえば、3で割り切れるバイナリの数値を受け入れるチューリングマシンを持っていて、bianryの数字ではない入力を渡すなら（たとえば、 "apple sauce"）、我々はまだ出力について推論することができますプログラムの