About
This site contains an evaluation service, exercises and the specifications for the programming languages LOOP, GOTO and WHILE. The languages are similar to the ones used in Uwe Schöning's book "Theoretische Informatik  kurzgefasst". Such languages are often found in introductory treatments of theoretical computer science as a means to introduce the concept of computability.
Specifications
These are the specifications for the programming languages LOOP, GOTO & WHILE in strict and extended versions. The extended versions are more or less freely designed by myself.
Remember, with either language you can only implement functions
whose codomain are the natural numbers and whose domain are the natural numbers
to the power of n, where n is the number of arguments. Also,
every variable is by default initialized to 0
and arguments, if
any, are stored in x1, …,xn
. That means, providing the argument
list 4,87,3
is the same as prepending x1 := 4; x2 := 87, x3
:= 3
to the top of your program. Also, note that each language is
case sensitive!
LOOP
An exemplary (extended and pointless) LOOP program looks as follows:
x4 := abc + y * 4; IF hg != 7  hg != 7 THEN LOOP x4  (x4 + 1) DO x0 := 1 END ELSE x0 := counter END
Syntax
The syntactical components are
 Variables:
x0
,x1
,x2
,x3
,x4
,...  Constants:
0
,1
,2
,3
,4
,...  Operators:
+
and
 Separators:
;
and:=
 Keywords:
LOOP
,DO
andEND
Let xi
and xj
be variables and let c
be
a constant. Then
xi := xj + cand
xi := xj  care LOOP programs.
Let P1
and P2
be LOOP programs. Then
P1; P2is a LOOP Program.
Let P
be a LOOP program and let xi
be a variable.
Then
LOOP xi DO P ENDis a LOOP Program.
Semantics
Let P
be a LOOP Program. P
computes a function
f: ℕ ^{k} → ℕ like so:
At the beginning of the computation the arguments
n_{1}, …, n_{k} ∈ ℕ
are to be found in the variables x1
, …,xk
. All other
variables have the starting value 0. P
is executed as follows:
 By executing the program "
xi := xj + c
"xi
is assigned the value ofxj + c
.  By executing the program "
xi := xj  c
"xi
is assigned the value ofxj  c
if the value is nonnegative. Otherwisexi
is assigned 0.  By executing the program "
P1; P2
" at firstP1
is executed and after thatP2
.  The execution of the program "
LOOP xi DO P' END
" happens as follows: The ProgramP'
is executed as often as the value ofxi
has been at the Beginning. That means, assignments toxi
insideP'
do not influence the number of repetitions.
The result of P
's execution is the value of x0
or put in another way
f(n_{1}, …, n_{k}) = Value of x0
after execution .
A function f: ℕ ^{k} → ℕ is called LOOPcomputable if there exists a LOOP program that computes f as described above.
Extensions
Variables can be named arbitrarily. The only restrictions are that they begin
with a letter and are not a keyword, e.g. counter4
is a valid
variable identifier. Apart from that the following LOOP programs are all valid
and have the respective intuitive semantics:
xi := xj
(stands forxi := xj + 0
)xi := c
(stands forxi := xj + c
wherexj
is an unused variable)xi := aexp
whereaexp
is an arbitrary arithmetic expression consisting of variables, constants, (optional) parantheses and operators (+
,
,*
,/
,^
and%
) like for exampley * (hg + 8 / x8)  2 % 4
.LOOP aexp DO P END
whereaexp
is an arbitrary arithmetic expression.IF xi = 0 THEN P END
IF !(xi < xj && !(xk != 3)) THEN P1 ELSE P2 END
IF bexp THEN P END
wherebexp
is an arbitrary "boolean" expression consisting of variables, constants, (optional) parantheses, relational operators (<
,<=
,>
,>=
,=
and!=
) and boolean operators (&&
,
and!
).IF bexp THEN P1 ELSE P2 END
Also, you are allowed to insert comments in your source code. The syntax is
similar to Java's comment syntax, i.e. //
introduces a comment
whose scope ends at the next line and /* */
can be used for
multiline comments.
GOTO
An exemplary (extended and pointless) GOTO program looks as follows:
M1: x4 := abc + y * 4; Cool: IF hg != 7  hg != 7 THEN GOTO M1 ELSE HALT END; GOTO Cool; M42: HALT
Syntax
A GOTO program is a succession
M1: A1; M2: A2; ⋮ Mk: Ak
where Mi
is a so called label and Ai
is an
instruction. Possible instructions are:
 Value assignment:
xi := xj ± c
(xi
,xj
are variables,c
is a constant)  Jump:
GOTO Mi
 Conditional Jump:
IF xi = c THEN GOTO Mj
 Stop instruction:
HALT
The last instruction is either a stop instruction or a jump.
Semantics
The execution of a GOTO program starts with the first instruction. The execution of instructions of each type is as follows:
 "
xi := xj ± c
": The value ofxi
becomesxj ± c
and the next instruction is executed.  "
GOTO Mi
": Proceed with the instruction with labelMi
.  "
IF xi = c THEN GOTO Mj
": If the value ofxi
is equal toc
proceed with the instruction with labelMj
. Otherwise the next instruction is executed.  "
HALT
": Stop the execution of the program.
A jump to a label that is not existent in the program is not defined.
Let P
be a GOTO Program. P
computes a function
f: ℕ ^{k} → ℕ like so:
At the beginning of the computation the arguments
n_{1}, …, n_{k} ∈ ℕ
are to be found in the variables x1
, …,xk
. All other
variables have the starting value 0.
f(n_{1}, …, n_{k})
is the value of x0
after execution if P
terminates. Otherwise
f(n_{1}, …, n_{k}) is undefined.
A function f: ℕ ^{k} → ℕ is called GOTOcomputable if there exists a GOTO program that computes f as described above.
Extensions
The program doesn't have to end with a jump or a stop instruction. Labels can
be named arbitrarily or can be omitted altogether. Note, tough, that labels
must be unique. IF
statements must be completed with the lexeme
END
because they can contain several statements. Furthermore,
a HALT
statement may appear in the body of an IF
.
Apart from that, all extensions from the LOOP language  except for the
LOOP
construct which is not present in the extended GOTO language
 apply to the extended GOTO language.
WHILE
The WHILE language is an extension of the LOOP language. An exemplary (extended and pointless) WHILE program looks as follows:
x4 := abc + y * 4; IF hg != 7  hg != 7 THEN WHILE !(x4 = x4 + 1) DO x0 := 1 END ELSE x0 := counter END
Syntax
Apart from the LOOP
construct which is not part of the WHILE
language the syntax is the same as that of LOOP. Additionally, a new keyword
(WHILE
) with the accompanying syntactical construct, namely the
WHILE
loop, is introduced.
Let P
be a WHILE program and let xi
be a variable.
Then
WHILE xi != 0 DO P ENDis a WHILE program.
Semantics
The execution of "WHILE xi != 0 DO P END
" happens so, that the
program P
is executed as long as the value of xi
is not equal to 0.
Let P
be a WHILE Program. P
computes a function
f: ℕ ^{k} → ℕ like so:
At the beginning of the computation the arguments
n_{1}, …, n_{k} ∈ ℕ
are to be found in the variables x1
, …,xk
. All other
variables have the starting value 0.
f(n_{1}, …, n_{k})
is the value of x0
after execution if P
terminates. Otherwise
f(n_{1}, …, n_{k}) is undefined.
A function f: ℕ ^{k} → ℕ is called WHILEcomputable if there exists a WHILE program that computes f as described above.
Extensions
Apart from the LOOP
related extensions  since the WHILE language
has no LOOP
construct  the LOOP extensions are all valid WHILE
extensions. Additionally, the head of a WHILE
loop can have an
arbitrary boolean expression, e.g. WHILE xyz != 9  u = 8 DO P END
is a valid (extended) WHILE program.
Exercises
You do not really know what to do on this website? Fear not, for I have
a quest for you whose accomplishment will award you with enlightment and
invincibility! To solve this quest you must simply solve each exercise to the
best of your knowledge. All answers to this questions can be found out by
either thinking, executing/transforming code with the evaluation service or by
looking at the source code
of the interpreters. You are allowed to use the knowledge from previous
exercises, e.g. if you showed how an IF
can be transformed into
strict LOOP program you can use this knowledge throughout the following
exercises unless it is explicitly forbidden in an exercise.
Various sources for the exercises have been used. Some exercises were my idea whereas others were taken from Prof Dr. Heribert Vollmer's introductory course in theoretical computer science and yet others from Project Euler.
 Show that the function f(x_{1}, x_{2}): = x_{1} + x_{2} is LOOPcomputable by writing a (strict) LOOP program that computes this function.
 Show that the function f(x_{1}, x_{2}): = x_{1}  x_{2} is LOOPcomputable. Here f really stands for max{x_{1}  x_{2}, 0}.
 Write a LOOP Program that computes the sum of the numbers 1 to 1000.

Write a LOOP Program that is equivalent to the following construct:
IF xi != 0 THEN P END

Write a LOOP Program that is equivalent to the following construct:
IF xi = 0 THEN P1 ELSE P2 END
 Show that the function f(x_{1}, x_{2}): = x_{1} ⋅ x_{2} is LOOPcomputable.
 Show that the function f(x_{1}): = x_{1}! is LOOPcomputable.
 Show that the function f(x_{1}, x_{2}): = x_{1}^{x2} is LOOPcomputable.

Write a LOOP Program that is equivalent to the following construct:
IF xi = xj THEN P END

Write a LOOP Program that is equivalent to the following construct:
IF xi > xj THEN P1 ELSE P2 END

Write a LOOP Program that is equivalent to the following construct:
IF xi >= xj THEN P1 ELSE P2 END
 Show that the function f(x_{1}, x_{2}): = x_{1} / x_{2} is LOOPcomputable. Here "/" stands for integer division, i.e. the rest is discarded.

Show that the function
f(x_{1}, x_{2}): = x_{1}%x_{2} = x_{1} mod x_{2}
is LOOPcomputable. From here on you are allowed to use arbitrary, compound
arithemtic expressions like
x0 := x1 / (x2 + x3) % c
. 
Write a LOOP Program that is equivalent to the following construct:
IF r1 && r2 THEN P END

Write a LOOP Program that is equivalent to the following construct:
IF r1  r2 THEN P END
From here on you are allowed to use arbitrary, compound boolean expressions (inIF
constructs). 
Once again write a LOOP program that computes the function
f(x_{1}, x_{2}): = max{x_{1}  x_{2}, 0}.
But this time do it by only using addition and perhaps the
IF
construct.  Write a LOOP program that finds the sum of all the multiples of 3 or 5 below 50.
 Write a LOOP program that finds the difference of the sum of the squares of the first 30 numbers and the square of the sum of the first 30 numbers.
 Show that the function f(x_{1}): = ∣bin(x_{1})∣ is LOOPcomputable. For example, f(1): = ∣1∣ = 1, f(2): = ∣10∣ = 2, f(5): = ∣101∣ = 3.

Write a LOOP program that returns 1 if
x1
is a square and 0 otherwise. 
Write a LOOP program that returns 1 if
x1
is a prime number and 0 otherwise. 
Which oneargument function does the following LOOP program compute:
LOOP x1 DO t := 0; LOOP c DO t := t + c END; IF t = x1 THEN x0 := c END; c := c + 1 END

For some reason you are sick of using the
LOOP
construct in the strict LOOP language. You want to rewrite all your LOOP programs to be free of that dreadedLOOP
. None of your programs use arguments. How could you do it? 
Is the following WHILE program LOOPcomputable? Justify your answer.
WHILE x1 != 1 DO x1 := x1  2 END; x0 := x1
 A number is perfect if it is the sum of its factors that are smaller than said number. The first three perfect numbers are thus 6, 28 and 496. Show that the function f(x_{1}): = the x_{1}th perfect number is WHILEcomputable.
 Show that the function f(x_{1}): = the x_{1}th fibonacci number is WHILEcomputable.

For some reason you are now sick of using the
WHILE
construct in the extended WHILE language. You want to rewrite all your WHILE programs to be free of that dreadedWHILE
. You know for sure that none of yourWHILE
loops does more than ten iterations. How could you do it principally?  Show that the function f(x_{1}, x_{2}): = x_{1} + x_{2} is GOTOcomputable by writing a strict GOTO program that computes this function.

Write a strict GOTO program that is equivalent to the following construct:
IF xi = c THEN HALT END

Which oneargument function does the following strict GOTO program compute:
M1: IF x1 = 0 THEN GOTO M5; M2: x0 := x0 + 1; M3: x1 := x1  x0; M4: GOTO M1; M5: HALT
 Provide an equivalent WHILE program to the previous GOTO program and justify its correctnes.

Describe an algorithm for correctly relabeling the code of an extended GOTO program when transforming it to the strict version! Consider all cases!
Try your algorithm on this snippet:
x0 := x1 + 3; Nt: IF x0 = 5 THEN GOTO M4 END; M3: x0 := x2 + 3; Mx: GOTO M5; M4: x0 := x3 + 3; M5: x0 := x4 + 3
To test if your algorithm is correct simply compare the output of the evaluation service for the transformation of the given code with your handtransformed code.

How to generally transform the strict
LOOP
construct into an equivalent WHILE program? 
How to generally transform the strict
LOOP
construct into an equivalent GOTO program?  How to generally transform a strict WHILE program into an equivalent GOTO program?
 How to generally transform a strict GOTO program into an equivalent WHILE program?
 By what factor in the worst case does the running time of a program that is first written in GOTO and then automatically transformed to WHILE increase?
 Bonus: Which of the languages is Turingcomplete? Proof in each case whether the language is Turingcomplete or not.