私はトラブルこれを解決持っていますLが決定可能であるならば、我々はそのL *はまた、チューリングマシンを構築することにより決定可能であることを証明できることを知っているが、 :Lが決定不能である場合には、L *はまた、決定不能である を。 この文は真か偽ですか?クリーネスター決定不能
答えて
これは誤りです。 Lを決めることのできない言葉にする。 Rに長さ1のすべての文字列が追加された状態でLを定義します(まだLに含まれていない場合)。 Rにはアルファベットの長さ1のすべての文字列が定義されています。また、Lは決めることができないので、Rでなければなりません(決めることができない言語と有限の言語の和集合も決めることができません;以下のコメントを参照してください)。しかしR *には、アルファベットのすべての文字列、決定的な言葉が含まれています(実際、それは規則的です)。明確にするために、われわれはちょうど、決めることのできない言語から、その主張の反例である別のものを構築する方法を示した。
決めることができない言語と有限言語の和集合が決めることができないことを知るためには、Lが決定不能であり、Rが有限である場合、Lの組合Rは決定可能であると仮定する。つまり、L組合Rのメンバーシップを決めるTMがあります.Rが交差するRを決めるTMがあることはわかります.Rが有限であれば、それ以外のものとの交差もそうです。しかし、L =((L組合R)setminus R)組合(L Rと交差する):RはLのすべてまたはR
- L組合組合(L intersect R)はすべてLである。
決定可能な言語は集合差と組合によって閉じられるので、Lは決定可能でなければならず、矛盾でなければならない。だからL組合Rは決めることができないLと有限Rのために決めることができません。
でこれを尋ねる方が良いでしょう。 undecidabilityが閉鎖されているという事実が本当に必要です。そうではありません。しかし、ここではRは有限集合であり、有限数の要素を追加したり削除したりすることは決して(非)決定性を変えることはない。 –
@PeterLeupoldあなたが正しいです、私は正しい観察をするためにこれを修正します。 – Patrick87
- 1. 文字列(クリーネスター)
- 2. SwisscomDev/Cloudfoundryで不安定版/不安定版を解決する
- 3. SSISルックアップ - 不明なコードの決定
- 4. 決定木学習と不純物
- 5. バンドルが設定不可能
- 6. 不定記事を決定するためのJavascriptライブラリ
- 7. 目標到達不能、識別子解決はJSF 2.2
- 8. BeanCurrentlyInCreationExceptionについての解決不可能な循環参照
- 9. MCG002解決不可能な型参照 'System.ComponentModel.Design.IDesignerHost'
- 10. iPhoneは、さらに別の解決不可能なメモリが
- 11. プロジェクトビルドエラー:org.camunda.bpm.webappの解決不可能な親POM:camunda-webapp:[unknown-version]
- 12. 未解決のリンク不安定/ lp文書
- 13. テンソルフロー勾配の決定の決定性?
- 14. 不可能
- 15. AndroidのKivy:urlopenエラー[Errno 4]修復不可能な名前解決の失敗
- 16. http://start.spring.io/で作成されたMavenプロジェクトの解決不可能な親POM
- 17. Artifactory Gradle解決URLが不正確で不一致
- 18. FFMPEG不正なフレームサイズ、解決方法?
- 19. 到達不能エラーベクトル
- 20. 到達不能コード+
- 21. 不可能なwith_subelements
- 22. タブローログ機能不正
- 23. Eclipse、Javamail、Tomcat、およびソケット到達不能/ネットワーク到達不能?
- 24. {<M> | MはTMであり、| L(M)| = n}を決定する決定者が決定したら、決定者はn-1を決定する
- 25. カスケードシャドウマッピングルックアップ決定/ gl_FragCoord.z
- 26. 決定子カウント
- 27. バイナリ決定図
- 28. グリッドカラムタッチ決定アルゴリズム
- 29. 決定7
- 30. この言語は決定可能ですか?
https://cs.stackexchange.com/ – harold