言語が認識可能なIFFを計算可能に列挙可能な証明

Question

この証明については非常に小さい質問、私はSipser'sのT.21として、そして私の講義で見つけた。

方向のみ「IF」方向に、チューリングマシン $ m $ がいくつかの言語を認識している $ l $ 。 $ s_1、s_2、s_3、\ dots $

のすべての文字列をリストアルファベットのすべての文字列をリストします。

次に列挙子を構築します。 $ e $ ごとに$ i= 1,2,3、\ dots $ $ i $ 手順の場合は、 を実行します。各入力 $ s_1、s_2、s_3、\ dots、s_i $ 。次に、 $ m $ によって受け入れられている $ s_j $ を印刷します。 $ E $ が必要なものです。

今、文字列が有限であることを知っているので、 $ iのために を実行する必要があります。 $ i $ 文字列の$ 手順で実行できる場合は、 $ i $ -th string？不必要な合併症のように感じます。

p.S。もう一つの質問はこれについて尋ねられましたが、それは異なる疑いに取り組んでいました： の質問「定理のための「言語の部分」の場合のみ「列挙体が列挙している場合のみ」列挙体がそれを列挙します。 "

Answer 1

$ m $ を実行した場合は、$ i $ -th thth文字列で停止することはありません。たくさんのアルゴリズムは動けなくなります。このアイデアは、 $ m $ が $ i $ -th文字列を停止した場合、SPAN CLASS="Math-Container"> $ J $ 手順で、 $ \ max（i、j）$ 番文字列