PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program:

$$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \ R \ \text{END}$$

First $P$ is executed. Then $Q$ is executed until $x_0 \neq 0$. Finally $R$ is executed. I have to prove that PRE-WORK-POST is Turing complete and I have chosen to prove that I can simulate any WHILE program through a PRE-WORK-POST program. I'm stuck on one of the tasks. Given that $P1$ and $P2$ are both WHILE program, then $P1;P2$ is also a WHILE program (by definition). How can I simulate this using PRE-WORK-POST? I'm not really sure how I can do this since LOOP programs don't allow for nested loops.

  • $\begingroup$ I will bet that you misunderstood LOOP (and also, your description of it is insufficient). Is there a source where we can have at the complete specification of LOOP? It does not seem to be the Wikipedia page on LOOP. $\endgroup$ – Andrej Bauer Jan 13 at 14:58
  • $\begingroup$ This seems to be a duplicate of Prove that PRE-WORK-POST is Turing Complete. Where the question has no answer either. $\endgroup$ – Hendrik Jan Jan 13 at 15:33
  • $\begingroup$ In our lecture LOOP has the basic programs of: 1) Addition and Subtraction, 2) P1;P2, 3) LOOP $x_i$ DO P END. WHILE is defined as being able to do everything LOOP can with the addition of WHILE $x_i \neq 0$ DO P END. I need to simulate all WHILE programs using a Pre-WORK-POST program. I have done everything except the nested WHILE loops. That's what I'm asking here. $\endgroup$ – salami sauce Jan 13 at 16:46
  • $\begingroup$ And that's also the definition we are given in the exercise. $\endgroup$ – salami sauce Jan 13 at 16:47
  • $\begingroup$ This is basically the Kleene normal form. $\endgroup$ – Emil Jeřábek Jan 13 at 20:12

Your Answer

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

Browse other questions tagged or ask your own question.