# Is the halting problem always decidable for non-universal programs?

For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ halts on $I$?

Some concrete definitions:
A program $P$ that takes some data type $D$ as input is computable iff there exists some total computable function $h$ that takes a input string and returns a $D$, and some Turing machine $T$, which takes a binary string, such that $P(h(I)) \cong T(I)$ for all strings $I$. "$\cong$" includes both not halting as well as both producing the same output.

A program $P$ that takes some data type $D$ as input is universal iff there exists some total computable function $f$ that takes both a description of a Turing Machine and an input string and produces something of type $D$ such that for every Turing machine $T$ and every string $I$, $P(f(T, I)) \cong T(I)$.

• Odd thought: but does anything prevent us from defining "muted Turing Machines" or something which are defined as identical to Turing Machines but may only halt with a completely blank tape? Then we cannot decide halting because it's equivalent to the original halting problem but we cannot simulate arbitrary TMs because we cannot produce output? Maybe? – Daniel Gratzer Jan 14 '16 at 21:09
• That is very similar to another question I asked a while ago. What I got from it is that even if it doesn't halt you can encode the sequence of states it goes through somehow as output. So you can do that for your muted Turing machine to get the behavior back. If that isn't possible, then it would satisfy my conditions, I think. – Fricative Melon Jan 14 '16 at 21:26
• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Feb 2 '16 at 7:38
• Please don't edit questions so that existing answers become meaningless. That's impolite, wasting people's time. For follow-up questions, create a new post. – Raphael Feb 2 '16 at 7:39

To answer the first part of your question - Two counter machines are not exactly Turing-complete. That is, there are some functions that cannot be computed with them, for certain counter-values. This is a very slight weakness, so 2CM are actually very close to being Turing complete, but still.

As for your suggested model - could you formalize it in more detail? It's not clear enough as it is.

• Unfortunately, this answer seems to fit the question no longer. I did not follow the history of the question; feel free to edit it so that your question remains valid but the question is still improved as much as possible (in the spirit of the OP). – Raphael Feb 2 '16 at 7:40

You might feel this is a cheat but consider the following "model". A program is a natural number and the meaning of program $P$ is as follows. If the Turing machine whose code is $P$ halts when started with a blank tape, then program $P$ just halts; otherwise, $P$ loops forever.

This is not Turing powerful because, up to operational equivalence, there are only two programs: one is equivalent to "halt" and the other to "loop forever". However, no Turing machine can decide, when given $P$, whether $P$ halts.

• Unfortunately, this answer seems to fit the question no longer. I did not follow the history of the question; feel free to edit it so that your question remains valid but the question is still improved as much as possible (in the spirit of the OP). – Raphael Feb 2 '16 at 7:40

a more limited version of automata used for verification are known as "counter machines" with some associated decidable problems, but also an undecidable halting problem (Theorem 6 p4).

• btw a simple example of a non-Turing complete "model of computation"/ analog that might be said to have "a decidable halting problem": determination of whether a word is accepted by an FSM/ is contained in a regular language. so the question cannot really be answered exactly without better formal definitions of the terms ie "non-Turing complete model of computation" and probably all rigorous attempts at such formal definitions will lead to simple implications/ conclusions (either that all such models have undecidable problems, or none do), similarly to Rices thm. – vzn Jan 18 '16 at 22:12

Yes. That is essentially base of a lot of work in formal methods/model checking in software engineering. See e.g.

It has been some time but IIRC Moshe Vardi gave a talk a few years ago at the Fields institute on their work on how they solve some hard problems about programs in practice. The intuition, if I remember correctly, was that you can define a parameter for programs and although the running time increase uncomputably as that parameter increases for programs that we care about in practice the parameter is rather small and as a result the problem is tractable in practice. I will add a link to their paper if I recall it.