ここにいくつかの真偽の質問があります：誰かがこれらに答えてください：
F（0）= 1とし、n> 0の場合はF（n）= 2 ^ F（n-1）とします。では、Fチューリングは計算可能ですか？
あいまいな文脈自由文法を持つ言語は、DPDAで受け入れることができません。これは本当ですか ？そうでない場合は、どの文法がそれです。
質問する
329 次
2 に答える
0
私は最初のものが本当だと思います。
チャーチチューリングの論文によると、計算可能な関数は、無制限の時間とストレージスペースが与えられた場合に機械計算装置を使用して計算できる関数です。同様に、この論文は、アルゴリズムを持つ関数はすべて計算可能であると述べています。
于 2012-12-07T02:36:21.743 に答える
0
（1）については、この質問を自問してください。この関数を計算できるコンピュータープログラムを作成できますか？もしそうなら、チャーチチューリングの論文によって、あなたは同じ計算を行うことができるTMがなければならないことを知っているので、関数は計算可能です。そうでない場合は、TMも関数を評価できないことがわかります。
（2）の場合、あいまいさは文法の特性であることを忘れないでください。同じ言語に対して複数の文法が存在する可能性があります。
お役に立てれば！
于 2012-12-07T02:55:17.103 に答える