Input language is

with args
into
Output:

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` and `END`

Let `xi` and `xj` be variables and let `c` be a constant. Then

```xi := xj + c
```
and
```xi := xj - c
```
are LOOP programs.

Let `P1` and `P2` be LOOP programs. Then

```P1; P2
```
is a LOOP Program.

Let `P` be a LOOP program and let `xi` be a variable. Then

```LOOP xi DO P END
```
is 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 n1, …, nk ∈ ℕ  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 of `xj + c`.
• By executing the program "`xi := xj - c`" `xi` is assigned the value of `xj - c` if the value is non-negative. Otherwise `xi` is assigned 0.
• By executing the program "`P1; P2`" at first `P1` is executed and after that `P2`.
• The execution of the program "`LOOP xi DO P' END`" happens as follows: The Program `P'` is executed as often as the value of `xi` has been at the Beginning. That means, assignments to `xi` inside `P'` do not influence the number of repetitions.

The result of `P`'s execution is the value of `x0` or put in another way f(n1, …, nk) = Value of `x0` after execution .

A function f: ℕ k → ℕ  is called LOOP-computable 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 for `xi := xj + 0`)
• `xi := c` (stands for `xi := xj + c` where `xj` is an unused variable)
• `xi := aexp` where `aexp` is an arbitrary arithmetic expression consisting of variables, constants, (optional) parantheses and operators (`+`,`-`,`*`,`/`,`^` and `%`) like for example `y * (hg + 8 / x8) - 2 % 4`.
• `LOOP aexp DO P END` where `aexp` 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` where `bexp` 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 of `xi` becomes `xj ± c` and the next instruction is executed.
• "`GOTO Mi`": Proceed with the instruction with label `Mi`.
• "`IF xi = c THEN GOTO Mj`": If the value of `xi` is equal to `c` proceed with the instruction with label `Mj`. 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 n1, …, nk ∈ ℕ  are to be found in the variables `x1`, …,`xk`. All other variables have the starting value 0.

f(n1, …, nk) is the value of `x0` after execution if `P` terminates. Otherwise f(n1, …, nk) is undefined.

A function f: ℕ k → ℕ  is called GOTO-computable 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 END
```
is 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 n1, …, nk ∈ ℕ  are to be found in the variables `x1`, …,`xk`. All other variables have the starting value 0.

f(n1, …, nk) is the value of `x0` after execution if `P` terminates. Otherwise f(n1, …, nk) is undefined.

A function f: ℕ k → ℕ  is called WHILE-computable 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.

1. Show that the function f(x1, x2):  = x1 + x2 is LOOP-computable by writing a (strict) LOOP program that computes this function.
2. Show that the function f(x1, x2):  = x1 - x2 is LOOP-computable. Here f really stands for max{x1 - x2, 0}.
3. Write a LOOP Program that computes the sum of the numbers 1 to 1000.
4. Write a LOOP Program that is equivalent to the following construct:
```IF xi != 0 THEN P END
```
5. Write a LOOP Program that is equivalent to the following construct:
```IF xi = 0 THEN P1 ELSE P2 END
```
6. Show that the function f(x1, x2):  = x1 ⋅ x2 is LOOP-computable.
7. Show that the function f(x1):  = x1! is LOOP-computable.
8. Show that the function f(x1, x2):  = x1x2 is LOOP-computable.
9. Write a LOOP Program that is equivalent to the following construct:
```IF xi = xj THEN P END
```
10. Write a LOOP Program that is equivalent to the following construct:
```IF xi > xj THEN P1 ELSE P2 END
```
11. Write a LOOP Program that is equivalent to the following construct:
```IF xi >= xj THEN P1 ELSE P2 END
```
12. Show that the function f(x1, x2):  = x1 / x2 is LOOP-computable. Here "/" stands for integer division, i.e. the rest is discarded.
13. Show that the function f(x1, x2):  = x1%x2 = x1 mod x2 is LOOP-computable. From here on you are allowed to use arbitrary, compound arithemtic expressions like `x0 := x1 / (x2 + x3) % c`.
14. Write a LOOP Program that is equivalent to the following construct:
```IF r1 && r2 THEN P END
```
15. 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 (in `IF` constructs).
16. Once again write a LOOP program that computes the function f(x1, x2):  = max{x1 - x2, 0}. But this time do it by only using addition and perhaps the `IF` construct.
17. Write a LOOP program that finds the sum of all the multiples of 3 or 5 below 50.
18. 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.
19. Show that the function f(x1):  = ∣bin(x1)∣ is LOOP-computable. For example, f(1):  = ∣1∣ = 1, f(2):  = ∣10∣ = 2, f(5):  = ∣101∣ = 3.
20. Write a LOOP program that returns 1 if `x1` is a square and 0 otherwise.
21. Write a LOOP program that returns 1 if `x1` is a prime number and 0 otherwise.
22. Which one-argument 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
```
23. 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 dreaded `LOOP`. None of your programs use arguments. How could you do it?

24. Is the following WHILE program LOOP-computable? Justify your answer.
```WHILE x1 != 1 DO
x1 := x1 - 2
END;
x0 := x1
```
25. 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(x1):  = the x1-th perfect number is WHILE-computable.
26. Show that the function f(x1):  = the x1-th fibonacci number is WHILE-computable.
27. 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 dreaded `WHILE`. You know for sure that none of your `WHILE` loops does more than ten iterations. How could you do it principally?

28. Show that the function f(x1, x2):  = x1 + x2 is GOTO-computable by writing a strict GOTO program that computes this function.
29. Write a strict GOTO program that is equivalent to the following construct:
```IF xi = c THEN HALT END
```
30. Which one-argument 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
```
31. Provide an equivalent WHILE program to the previous GOTO program and justify its correctnes.
32. 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 hand-transformed code.

33. How to generally transform the strict `LOOP` construct into an equivalent WHILE program?
34. How to generally transform the strict `LOOP` construct into an equivalent GOTO program?
35. How to generally transform a strict WHILE program into an equivalent GOTO program?
36. How to generally transform a strict GOTO program into an equivalent WHILE program?
37. 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?
38. Bonus: Which of the languages is Turing-complete? Proof in each case whether the language is Turing-complete or not.