1
$\begingroup$

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.

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is a loop program? $\endgroup$ – Yuval Filmus Jun 18 '13 at 18:24
  • $\begingroup$ This : en.wikipedia.org/wiki/LOOP_(programming_language) Except that in the version we use, can't can add more than 1 to a register. We actually use inc(ri) which is equivalent to "ri <- ri+1", where ri is the i'th register. $\endgroup$ – Über Lem Jun 18 '13 at 18:33
1
$\begingroup$

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

  1. Outline a LOOP program which simulates a given IF program. Seems pretty messy.
  2. 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):

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, in a loop program, the halting problem is decidable as loop programs ALWAYS halt... but where am I going with that ? Interpreters need to be able never to stop ?! $\endgroup$ – Über Lem Jun 19 '13 at 0:19
  • $\begingroup$ You are headed to a contradiction - assuming a universal LOOP program exists, something will go wrong. The proof is very similar to the one that the halting problem is undecidable - there you assume that you have a program solving the halting problem and obtain a contradiction. Mimic this argument. $\endgroup$ – Yuval Filmus Jun 19 '13 at 1:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.