特定の有限関数に対して停止の問題を解決できますか？

Question

それは十分に簡単な関数のために、のは、それはすべての可能な入力のために停止するかどう伝えることが可能である

function(boolean input){ 
    while(input){ 
    } 
} 

をしましょうというのが私の理解です。

上記の関数がfalseのため終了し、true. It's only impossible to solve the halting problem for an arbitrary function f , as of course you can evaluate haltingFinder（haltingFinder） `のために終了せず、基本的に逆説を作成することは容易にわかります。

私は理解していますか？

Answer 1

はい、もちろんあなたは正しいです。ループもなくても、それは常に停止します。通常の文脈自由言語のようなクラス全体では、停止問題は簡単です：対応する機械（有限オートマトン、イプシロン移動のないプッシュダウンオートマトン）は、入力語の長さに等しい数のステップしか作ることができず、したがって常に停止します。もちろん、単純な機能のために非停止計算を設計することはできますが、通常の言語用の無用なループを持つチューリングマシン。