patternMinor
Do there exist coding languages where the halting problem is solvable but not trivial
Viewed 0 times
problemthelanguageswherebuthaltingexistsolvabletrivialthere
Problem
Does there exist a coding language where
So languages that don't allow loops, even if finite are right out.
- It is always possible to determine whether a computer program will halt or run forever. And
- The answer is not always yes. (or always no)
So languages that don't allow loops, even if finite are right out.
Solution
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'.
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'.
Context
StackExchange Computer Science Q#126772, answer score: 3
Revisions (0)
No revisions yet.