0
$\begingroup$

Is the halting problem, only applicable for infinite languages?

I assume that if the language is finite, then we can search over all words?

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "applicable"? The halting problem makes sense for any language. $\endgroup$ – Yuval Filmus Jun 19 at 14:31
  • $\begingroup$ @YuvalFilmus I meant that if the language was finite, then you could scan all possible solutions? For example, if L has one element, then we can know if it will halt by checking if the input is equal to the one element in L? $\endgroup$ – WeCanBeFriends Jun 19 at 14:40
  • 1
    $\begingroup$ The halting problem accepts as input a (description of) a Turing machine $M$ and an input $x$, and the goal is to decide whether $M$ halts on $x$. If you fix $M$ then it's no longer the halting problem. $\endgroup$ – Yuval Filmus Jun 19 at 14:47
  • $\begingroup$ @YuvalFilmus What do you mean by "Fix M" ? To re-say what I think you said: The Halting problem is a problem that takes in any arbitrary Turing Machine and input. If this is correct, then if the M arbitrarily chosen is defined over a finite language, then can we not just check the set? $\endgroup$ – WeCanBeFriends Jun 19 at 14:52
  • 1
    $\begingroup$ The halting problem accepts as an input a Turing machine $M$ and an input $x$, and the goal is to decide whether $M$ halts on $x$. Another formulation fixes $x$: the input is just a Turing machine $M$, and the goal is to decide whether $M$ halts on the empty input (say). Anything else is not the halting problem. You mention "the language", but I'm not sure how it fits in this picture. $\endgroup$ – Yuval Filmus Jun 19 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.