HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthelanguageswherebuthaltingexistsolvabletrivialthere

Problem

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.

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

Context

StackExchange Computer Science Q#126772, answer score: 3

Revisions (0)

No revisions yet.