WHILE program

WHILE programs play a role in theoretical computer science , especially in connection with predictability .

properties

RAM-calculable , Turing-calculable , GOTO-calculable and WHILE-calculable are equivalent
LOOP-calculable WHILE-calculable ${\ displaystyle \ varsubsetneq}$
Kleen's normal form (every WHILE program can only use one while loop )

syntax

WHILE programs have the following syntax in modified Backus-Naur form :

${\ displaystyle {\ begin {array} {lrl} P & :: = & x_ {i}: = x_ {j} + c \\ & | & x_ {i}: = x_ {j} -c \\ & | & P; P \\ & | & \ mathrm {LOOP} \, x_ {i} \, \ mathrm {DO} \, P \, \ mathrm {END} \\ & | & \ mathrm {WHILE} \, x_ {i} \ neq 0 \, \ mathrm {DO} \, P \, \ mathrm {END} \ end {array}}}$

The LOOP construct in this definition can also be dispensed with without reducing the number of WHILE-calculable functions. Finally, every LOOP expression can be emulated by a WHILE. However, dispensing with the LOOP means that not all WHILE programs can be brought into Kleen's normal form .

Explanation of the syntax

A WHILE program P consists of the symbols WHILE , LOOP , DO , END,: =, +, -,; ,, a number of variables and any constants c . ${\ displaystyle \ neq}$ ${\ displaystyle x_ {1}, x_ {2}, ...}$

Only four different statements are allowed, namely

the assignment of a variable by another variable, increased by a constant, for example

{\ displaystyle x_ {3}: = x_ {4} +10}

or reduced by a constant, for example

{\ displaystyle x_ {5}: = x_ {6} -300}

a LOOP statement that checks the value of a variable at the beginning and repeats a WHILE program accordingly, for example

{\ displaystyle \ mathrm {LOOP} \ quad x_ {7} \ quad \ mathrm {DO} \ quad x_ {7}: = x_ {7} +1 \ quad \ mathrm {END}}

It should be noted that with LOOP, a change in the variable value in the part program to be repeated has no effect on the number of repetitions of this part program.

a WHILE statement that queries a variable that is not equal to zero and contains a WHILE program between DO and END, for example

{\ displaystyle \ mathrm {WHILE} \ quad x_ {8} \ neq 0 \ quad \ mathrm {DO} \ quad x_ {8}: = x_ {8} +1 \ quad \ mathrm {END}}

The instructions are, in and of themselves, complete WHILE programs. Furthermore, the

Stringing together of WHILE programs, each separated by a semicolon, for example

{\ displaystyle x_ {9}: = x_ {9} +3; \ quad x_ {10}: = x_ {9} -2}

another WHILE program.

General

Every WHILE-calculable function is GOTO-calculable and vice versa as well as turing -calculable .

The set of all WHILE programs is also referred to as defined above. ${\ displaystyle \ mathrm {WHILE}}$

Kleenesche normal form for WHILE programs

Every WHILE-calculable function can be calculated by a WHILE program with only one WHILE loop.

Proof: Be any WHILE program. We first reshape as described in the section "Simulation by GOTO Programs" of this article in order to obtain an equivalent GOTO program . Then we transform the instructions in the section "Simulation by WHILE program" in the article GOTO program into an equivalent WHILE program . It should be noted here that the IF THEN END statements required for this construction can be simulated by LOOPs. By construction only has one WHILE loop. ${\ displaystyle P}$ ${\ displaystyle P}$ ${\ displaystyle P '}$ ${\ displaystyle P '}$ ${\ displaystyle P ''}$ ${\ displaystyle P ''}$

Consequences

The easily provable fact that every GOTO program can be converted into a WHILE program and vice versa has the consequence that it can be proven that any Pascal program can perform the same as any BASIC program. It also shows that any program can also be programmed in a structured manner without generating " spaghetti code ".

Simulation by GOTO program

Every WHILE program

{\ displaystyle \ mathrm {WHILE} \ quad x2 \ neq 0 \ quad \ mathrm {DO} \ quad P \ quad \ mathrm {END}}

can be simulated by the following GOTO program:

M1: IF x2 = 0 THEN GOTO M2;
    P;
    GOTO M1;
M2: ...

literature

Uwe Schöning : Theoretical Computer Science - in a nutshell . 5th edition. Spectrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 2.3 LOOP, WHILE and GOTO predictability.