Input language is



with args
into
Output:

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

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:

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:

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:

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:

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.