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