5
$\begingroup$

The halting problem says that a Turing machine cannot decide if another Turing machine halts.

However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO statements are simple to formally verify. FORTRAN is however not Turing complete.

What is the largest subset or class of halting programs that can be decided? Is there a class of such languages?

This blog entry seems to hint at the fact that since the compiler optimized the code by eleminating the while(1) loop, Fermat's last theorem is disproved by a compiler.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure there is such a thing as the largest subset, but you can check out primitive recursive functions, or the programming language BlooP invented by Hofstadter. $\endgroup$ – Pål GD May 11 '14 at 21:50
  • 2
    $\begingroup$ The halting problem is a problem in the sense of "task" ("I want you to do the problems in chapter 3 for the next class"), not a problem in the sense of "difficulty" ("The problem with Turing machines is that I can never find enough tape.") So, the halting problem is the following task: given a description of a Turing machine and its input, determine whether the machine halts with that input. The halting problem is undecidable, as you say. $\endgroup$ – David Richerby May 11 '14 at 22:07
  • 4
    $\begingroup$ "FORTRAN is however not Turing complete." As far as I can tell, this statement is incorrect. $\endgroup$ – David Richerby May 11 '14 at 22:08
  • $\begingroup$ I don't understand your central question: "What is the largest subset or class of halting programs that can be decided?" -- there is the class R of all total (i.e. always halting) programs, and if we restrict inputs to programs from this class the halting problem is trivially decidable. All other programs have inputs for which they don't halt. Should your question be, "What is the largest class of programs for which the halting problem is decidable?". If so, decidable by a machine from the class or by any TM? $\endgroup$ – Raphael May 12 '14 at 14:05
  • $\begingroup$ @WanderingLogic The set of all programs is countable, so in particular no set of programs is uncountable. $\endgroup$ – Yuval Filmus May 12 '14 at 16:27
6
$\begingroup$

There is no largest class of programs which have a decidable halting problem. If $L$ is such a class and $P \notin L$, then the class $L \cup \{P\}$ also has a decidable halting problem (why?). (This works since the class of all programs does not have a decidable halting problem.)

Responding to Raphael's comment, there is also no largest class of programs, up to finitely many exceptions, with a decidable halting problem. For each program $P$, let $L(P)$ be some infinite decidable set of programs equivalent to $P$ (for Turing machines, we can add dummy unreachable states, for example). Let $L$ be a class with decidable halting problem. I claim that there must be some $P$ such that $L(P) \cap L = \emptyset$. Otherwise, we could decide the halting problem for an arbitrary program $P$ by enumerating $L(P)$. Given a program $P$ such that $L(P) \cap L = \emptyset$, we can obtain a decider for $L \cup L(P)$, so that $L$ has infinitely many exceptions.

$\endgroup$
  • $\begingroup$ If that is how the question has do be read, I think it's reasonable to allow finitely many exceptions. $\endgroup$ – Raphael May 12 '14 at 14:05
  • $\begingroup$ @Raphael That doesn't help. $\endgroup$ – Yuval Filmus May 12 '14 at 16:27

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.