# Do there exist coding languages where the halting problem is solvable but not trivial

Does there exist a coding language where 1. It is always possible to determine whether a computer program will halt or run forever. And 2. The answer is not always yes. (or always no) So languages that don't allow loops, even if finite are right out.

• What do you mean by "computer language"? you mean a "coding language" or a whole new idea of what is "a computer"? Jun 5 '20 at 14:10
• What if you take a total programming language and then add a primitive infiniteloop? Then any use of infiniteloop will mean the program runs forever and complete absence of infiniteloop will mean the program will halt. Of course this language is not turing complete. Jun 5 '20 at 14:42
• @Labbekak Not quite enough ... you have to be able to check whether the looping command is actually executed. Jun 5 '20 at 14:58
• Aah very good point! Jun 6 '20 at 15:16
• @blademan9999 Your question surprised me. I thought it a bit silly at first, but not so. It remained in my mind and questioned the meaning of "trivial". Many things do not seem trivial, until you know how they work or how they were obtained. BTW, welcome to SE computer science. Jun 8 '20 at 14:18

In some sense, I think you can only have trivial answers. Consider some language L that meets your definition of halting being decidable, though not always terminating or always non-terminating. Given the halting decision procedure for L, we can always change that language L into an almost identical one L' that will always terminate, though by returning a new special value $$\perp$$ (read 'bottom'), when language L does not terminate. Now we can look at our contraption from the other end, and see L as a language derived from the always terminating language L', in a way that replaces all computations producing a specific result, namely $$\perp$$, by an infinite loop. So L is a trivial answer derived from L'.
That would be not difficult at all. We use something similar to a Turing machine with a small modification: As it runs it counts the number of steps performed. For the first $$10^{1000000}$$ steps it behaves like a normal Turing machine. But if it hasn’t halted by then, it keeps running forever.