turing-machineshalting-problem

Can the halting prοblem be sοlved for certain finite functions?


It is my understanding that for a sufficiently simple function, let's say

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

it is possible to tell if it will halt for any possible input.

It is easy to see that the above function will terminate for false and not terminate for true. It's only impossible to solve the halting problem for an arbitrary functionf, as of course you can evaluatehaltingFinder(haltingFinder)` and essentially create a paradox.

Am I correct in my understanding?


Solution

  • Yes, of course you are right. Take a funtion that does not even have a loop: it will always halt. For entire classes like the regular and context-free languages the halting problem is trivial: the corresponding machines (finite automata, pushdown-automata without epsilon moves) can only make a number of steps equal to the input word's length and thus will always halt. Though, of course, you can design non-halting computations for simple funtions, e.g. a Turing Machine with useless loops for a regular language.