Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
    
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? – jozefg Jan 14 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 at 21:26
1  
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 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 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.

share|cite|improve this answer
    
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 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.

share|cite|improve this answer
    
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 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).

share|cite|improve this answer
    
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 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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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