This question is actually asking about the halting problem of Turing machines. Or in other words which of the constructs are needed to make a programming language Turing complete – when it becomes Turing complete, halting problem becomes undecidable for it.
To start with if we only have a linear sequence of instructions it is guaranteed to terminate because we only have a finite number of instructions to execute and individual instructions can be assumed to finish within a finite time. This is similar to deciding if a TM halts within a finite number of steps or not which is decidable.
The problem (of deciding whether a program halts or not) comes when there is a loop. Again, not all loops are a problem as shown below.
int n = 100;
for(int i = 0; i < n; i++)
{
...
}
Consider the above loop code. We can unroll the loop and repeat the loop body $100$ times and what we get is a linear sequence of instructions. So, the above loop does not affect the decision of halting.
Well, in the above paragraph I did not specify one crucial requirement for unrolling the loop. Assume we have a statement like
n = pow(n,x;)
where $x$ is any program variable. Now, $n$ is changing and so is the bound of the loop and we do not know how many times we have to unroll the loop. (This is similar to a Turing machine tape changing direction from right to left). Does this change make the halting decision undecidable now? $“$YES$”$ it does. Because now whatever a Turing machine can do we can do in this programming language – Turing complete. So, if we can decide halting problem for this programming language we are indirectly solving the halting problem of Turing machines – which is known to be unsolvable.
So now coming to the given constructs
- assignment $\checkmark$
- for loops where the loop parameter cannot be changed within the loop $\checkmark$
As described above this just translated to a finite number of sequential instructions when unrolled. Some people might be confused with loops like
int n = 0;
for(int i = 1; i > n; )
{
}
Here, if the loop body is not touching either $i$ or $n,$ the loop never terminates. But this decision (that it never terminates) can be decided easily by a written program (analyzing this is decidable and you can think of a C code to do it and equivalently we can have a Turing machine to decide this). So, the above loop even though being non-halting does not make the “halting decision” undecidable.
- if-then-else $\checkmark$
This just reduces one path (a set of instructions) from the linear sequence of instructions and hence does not affect the halting decision (assuming there are no other structures in either of the paths)
- forward go to $\checkmark$
Like, if-else this also just eliminates some set of instructions.
- arbitrary go to $❌$
This can simulate a for loop and so can cause problem in deciding halting.
- non-recursive procedure call $\checkmark$
Each of the called procedure contributes to the number of executed instructions but since there is no recursion they’ll eventually halt as long as each of the called procedures halt.
- recursive procedure/function call $❌$
This will also run into the same problem of a loop where the loop variables are changed inside the loop body. We may not be able to determine if the sequence of recursive calls ever terminates.
- repeat loop $❌$
Similar to a for loop if the looping condition is changed within the loop body this can make the halting decision undecidable.
Correct Option: B.
