# How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?

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.

• 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. Jan 13 at 14:58
• This seems to be a duplicate of Prove that PRE-WORK-POST is Turing Complete. Where the question has no answer either. Jan 13 at 15:33
• 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. Jan 13 at 16:46
• And that's also the definition we are given in the exercise. Jan 13 at 16:47
• This is basically the Kleene normal form. Jan 13 at 20:12