edited by
12,481 views
31 votes
31 votes

Given the programming constructs

  1. assignment
  2. for loops where the loop parameter cannot be changed within the loop
  3. if-then-else
  4. forward go to
  5. arbitrary go to
  6. non-recursive procedure call
  7. recursive procedure/function call
  8. repeat loop,

which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language

  1. $\text{(ii), (iii), (iv)}$
  2. $\text{(v), (vii), (viii)}$
  3. $\text{(vi), (vii), (viii)}$
  4. $\text{(iii), (vii), (viii)}$
edited by

5 Answers

Best answer
21 votes
21 votes

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

  1. assignment $\checkmark$
  2. 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.

  3. 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)
  4. forward go to $\checkmark$
    Like, if-else this also just eliminates some set of instructions.
  5. arbitrary go to $❌$
    This can simulate a for loop and so can cause problem in deciding halting.
  6. 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.
  7. 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. 
  8. 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.

selected by
25 votes
25 votes

Answer is (B).

Arbitary goto,recursive call and repeat may enter infinite loop,and hence terminates program may not be able to answer if 'the program does terminate'.

edited by
10 votes
10 votes
Eliminating options:-

Looking at the given list,7 and 8 will definitely in the answer so we can eliminate option 1 on this base.

Now we are left with 2,3,4 option.In which 2 items 7,8 are there in every option.So we just need to check 5,6,3 to get the answer.

If-else is just a block of constant set of statements,hence it cannot will not cause any looping.

Also,,Non recursive procedure call will not cause any looping in the program.

Now arbitrary goto can cause looping.Assume i have following code:-

LABEL:- statement 1

              statement 2

            GOTO LABEL. // Loop infinite

So based on this we can conclude b is the correct answer.
1 votes
1 votes

Hi @Arjun Sir and every one , i think 

  1. non-recursive procedure call can also create non terminating program 

A()

 { 

B()

}

B()

{

A()

}

Answer:

Related questions

54 votes
54 votes
3 answers
4
Kathleen asked Sep 23, 2014
15,415 views
A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this proces...