チューリングマシンとチューリング完全言語とは何かについて少し知っていますが、よりよく理解するために、誰かがチューリング完全ではない言語の例を挙げてもらえますか？（たぶん、チューリングではないマシンでも？）
3837 次
2 に答える
12
正式な定義では、以下のみで構成される正規表現。
- 連結（ab）
- 無制限の繰り返し（a *）
- 交互（a | b）
- グループ化（（ab）|（cd））
正規言語のみを認識できます。チューリング完全プログラミング言語は、帰納的可算言語を認識できます。
例として、正規表現では、文字列が一致する括弧のペアで構成されているかどうかを判断できません。たとえば、チューリング完全プログラミング言語では可能ですが、拒否されて()(())いる間は受け入れられます。()((())()
（最新のプログラミング言語の正規表現は、正規表現の正式な学術的定義よりも強力であることに注意してください。チューリング完全なものもあります。）
于 2010-08-30T12:42:04.340 に答える
3
正規言語（正規表現として記述できる言語）は、チューリング完全ではありません。
XMLやJSONのようなマークアップ言語（計算ではなくデータの記述に使用される）はチューリング完全ではありません。
于 2010-08-30T12:37:58.020 に答える