1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ What do you mean by "computer language"? you mean a "coding language" or a whole new idea of what is "a computer"? $\endgroup$ – nir shahar Jun 5 '20 at 14:10
  • $\begingroup$ 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. $\endgroup$ – Labbekak Jun 5 '20 at 14:42
  • $\begingroup$ @Labbekak Not quite enough ... you have to be able to check whether the looping command is actually executed. $\endgroup$ – babou Jun 5 '20 at 14:58
  • $\begingroup$ Aah very good point! $\endgroup$ – Labbekak Jun 6 '20 at 15:16
  • $\begingroup$ @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. $\endgroup$ – babou Jun 8 '20 at 14:18
3
$\begingroup$

I think I understand what you are trying to ask. But you may have to work harder on the asking to get a non-trivial answer. As it stands, your question has a trivial answer. Take a language that always terminate, and add a command that never terminates and is syntactically constrained to be used first if at all in a program. To check termination, you only have to check whether the program contains the non-terminating command.

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'.

$\endgroup$
1
$\begingroup$

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.

Obviously decidable, except that running the machine for that many steps is impossible.

$\endgroup$
1
  • $\begingroup$ What would be the difference if you considered only the first 10 steps? That would also be an answer. Technically the same as the one you are giving. What is the point of the big number? $\endgroup$ – babou Jun 7 '20 at 23:32

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.