Turing認識可能な言語は決定可能かどうか？

文字列を非短縮長で列挙することが可能な場合、チューリングで認識可能な言語を決定可能にすることはできますか？Turing認識可能な言語は決定可能かどうか？

私はそれが無限に行くことができないと思うし、これで決めることができないでしょうか？

2017-05-08 PTN

にこれを移動してください（古典的な意味で）知っていることを意味しhttps://cstheory.stackexchange.com/ –

移動 https://cstheory.stackexchange.com/questions/38168/a-turing-recognizable-language-is-decidable-or-not – PTN

認識可能な言語は常に決定可能です。あなたの質問は多分：列挙できない列挙可能なすべての言語が非可降順でデシジョン可能なのでしょうか？答えは「はい」です。 –

質問は、無秩序な流れの要素Sの順序付けられた要素の検索についてです：非常に自然なアルゴリズムの質問。

この問題は、やや卑劣な方法ですが、確かに決定可能です。あなたは事件ごとに理由を付ける必要があります。 Sの要素が上限を持つ場合、Sは有限であるため、有限集合はすべて決定可能であるため、決定可能です。反対に、Sに束縛がない場合、それは任意の数よりも大きな要素を含んでいます。だから、wを探しているならw（それが存在しなければならない）より大きいか等しい要素を見つけてwと比較するまで列挙すれば十分です。

しかし、証拠は建設的ではありません。セットは有限かどうか。これは、あなたがそこに必見は、いくつかのプログラムがSを決定存在していますが、S. Aかなりイライラする状況を列挙コードからそれを導出する方法がないこと:)

出典

2017-05-11 18:36:09

私はあなたが決定者を導く方法がないと言っている限り、行きません。列挙子があると仮定すると、2番目のテープに検索語を書き込み、最初の列に列挙し、テープを比較しながら列挙する列挙型の2つのテープTMを構築できます。 2テープTMがシングルテープTMと同等であるという建設的な証拠があります。短縮されていない順にLを列挙するTMが与えられれば、単一テープの決定子を構築することができます。建設的でない部分は、そのような列挙子が存在すると仮定することですが、これは仮説として当然のことです。 – Patrick87

@パトリック私はあなたに従っていません。あなたはあなたが探しているものよりも大きな要素を見つけることは確実ではありません（あなたが無限であることを知っていない限り、あなたはそうしない）ので、いつ停止するのか分かりません。 –

ああ、あなたが今言っていることが分かります。あなたが正しいです。 – Patrick87

Turing認識可能な言語は決定可能かどうか？

答えて

関連する問題