Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra Is it possible to write a universal loop program for if-then &amp; loop programs and it is possible to write a universal while program for while programs?


Long version and some background:

Before anyone asks, YES, it is a homework and I am not here to find an answer, but only clues to help me get this question right !

I'll translate the question from French :


  We call a universal program (also called interpreter) a program that
  accepts, as an input, another program and simulates it to produce the
  output of this simulated program. A universal program can also be used
  to simulate programs written in this very same language or in another
  language.
  
  You can suppose, using Gödel's coding, that the program to be
  simulated is given to the universal program in the register r1, and
  the input on which this program but be simulated in the register r2.
  The coding of the program could simply give out the characters of the
  program to be simulated in a table as well as its input registers in
  another table.
  
  Answer the following questions:
  
  a. It is possible to write a universal loop program for if-then
  programs?
  
  b. Is it possible to write a universal loop program for loop
  programs?
  
  c. Is it possible to write a universal while program for while
  programs? To reach a satisfying answer/proof lever, you could use
  the Church-Turing thesis.


Now the question, is where do I start with this ? My head's going in every direction at the same time, I'm just going crazy.

NOTES :

if-then programs are defined like this :

We consider a if-then program to be defined like a loop program, excepted that there are no loops, but an instruction "if rj then []" (rj is the register "rj", the j'th register)

I know for sure this has something to do with imbricated loops...

Any clues would be greatly appreciated !

Thanks a lot
For part (a), there are (at least) two approaches:


Outline a LOOP program which simulates a given IF program. Seems pretty messy.
IF programs can be simulated by a WHILE program, i.e. they are recursive. Moreover, the running time of such a simulator is very manageable. A recursive function with a primitive recursive bound on the running time is primitive recursive, and so implementable as a LOOP program.


For part (b), there are again two approaches (leading to the same result):


Suppose that you had a universal LOOP program. Try running the argument used to prove that the halting problem is undecidable, and see what you get.
The running time of every LOOP program is on some level of the primitive recursive hierarchy, and the latter is strict and has infinitely many levels. Consider the running time of a universal LOOP program and see what happens.


Part (c) is about universal Turing machines.