GATE CS 1999 Q2.5 — Programming in C

According to Turing's Halting Problem, if a programming language is Turing-complete, it is impossible to write a program in that language that decides whether any arbitrary program in the same language terminates.

To make the halting problem decidable (i.e., to be able to write a terminates function), the programming language must be restricted such that every program written in it is guaranteed to terminate. If all programs are guaranteed to terminate, the terminates function becomes trivial (it can simply always return true).

Let us analyze which constructs can cause non-termination (infinite loops or infinite recursion):

• (i) assignment: Safe. It executes in constant time and terminates.
• (ii) bounded for loops: Safe. Since the loop parameter cannot be modified within the loop, the loop is guaranteed to run a fixed, finite number of times.
• (iii) if-then-else: Safe. It only introduces conditional branching with no looping.
• (iv) forward go to: Safe. Because jumps can only go forward, it is impossible to create a loop.
• (v) arbitrary go to: Unsafe. Backward jumps can be used to create infinite loops.
• (vi) non-recursive procedure call: Safe. Without recursion, the function call graph is a Directed Acyclic Graph (DAG), guaranteeing termination.
• (vii) recursive procedure/function call: Unsafe. It can lead to infinite recursion.
• (viii) repeat loop: Unsafe. It is a conditional loop that can run infinitely if the termination condition is never met.

Thus, to guarantee termination, we must exclude the constructs (v), (vii), and (viii).