Может ли решающая проблема быть решена для определенных конечных функций?

Question

Это мое понимание того, что для достаточно простой функции, скажем

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

можно сказать, если он остановится для любого возможного ввода.

Легко видеть, что данная функция будет прекращена для false и не прекращать для true. It's only impossible to solve the halting problem for an arbitrary function е , as of course you can evaluate haltingFinder (haltingFinder) `и по существу создать парадокс.

Правильно ли я в своем понимании?

Answer 1

Да, конечно, вы правы. Возьмите funtion, который даже не имеет цикла: он всегда будет остановлен. Для целых классов, таких как обычные и контекстно-бесплатные языки, проблема остановки тривиальна: соответствующие машины (конечные автоматы, pushdown-automata без движений epsilon) могут делать только несколько шагов, равных длине входного слова, и поэтому всегда будут останавливаться. Хотя, конечно, вы можете проектировать не останавливающиеся вычисления для простых функций, например. Машина Тьюринга с бесполезными петлями для обычного языка.