Program LOOP

Program LOOP – jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.

• Programy LOOP jako model są znacznie ograniczone w możliwościach przedstawiania funkcji. (zobacz: składnia)
• Liczba funkcji obliczalnych za pomocą LOOP jest mniejsza niż liczba funkcji obliczalnych za pomocą maszyny Turinga. Przykładem funkcji obliczalnej za pomocą maszyny Turinga, a której nie da się przedstawić za pomocą LOOP jest funkcja Ackermanna.
• Programy LOOP przedstawiają funkcje totalne.

Programy LOOP składają się z symboli: LOOP, DO, END, +, -, :=, ; oraz dowolnej liczby zmiennych i stałych, przy czym stałe są elementami zbioru liczb naturalnych.

Program P jest syntaktycznie zdefiniowany w notacji BNF jako:

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

gdzie:

• ${\displaystyle c}$ – stała,
• ${\displaystyle x_{i},}$ ${\displaystyle x_{j}}$ – zmienne,
• ${\displaystyle P_{1},}$ ${\displaystyle P_{2}}$ – programy LOOP.

Wszystkie użyte w danym programie zmienne zostają zainicjalizowane przed wykonaniem programu. Zmienne nie zainicjalizowane bezpośrednio otrzymują domyślną wartość 0.

Wyrażenie postaci

 xi := xj + c

oznacza przyznanie zmiennej ${\displaystyle x_{i}}$ wartości otrzymanej poprzez dodanie zmiennej ${\displaystyle x_{j}}$ i stałej ${\displaystyle c.}$ Specjalnym przypadkiem jest tutaj sytuacja, gdzie wartość stałej ${\displaystyle c}$ jest równa zeru. Wtedy wartość zmiennej ${\displaystyle x_{j}}$ zostaje bezpośrednio przyznana zmiennej ${\displaystyle x_{i}{:}}$

 xi := xj + 0

Wyrażenie postaci

 xi := xj - c

oznacza przyznanie zmiennej ${\displaystyle x_{i}}$ wartości otrzymanej poprzez odjęcie stałej ${\displaystyle c}$ od zmiennej ${\displaystyle x_{j},}$ w przypadku gdy wartość stałej jest wyższa niż wartość zmiennej wynikiem odejmowania jest 0.

Kompozycja dwóch programów LOOP ma postać

 ${\displaystyle P_{1};}$ ${\displaystyle P_{2}}$

i oznacza, że program ${\displaystyle P_{1}}$ zostanie wykonany przed programem ${\displaystyle P_{2}.}$

Pętla LOOP ma postać

 LOOP ${\displaystyle x_{i}}$ DO ${\displaystyle P}$ END

przy czym liczba przebiegów programu jest z góry ustalona w zmiennej ${\displaystyle x_{i}}$ i nie ulega zmianie w trakcie wykonywania programu.

Następujący program LOOP przyznaje zmiennej x₀ sumę zmiennych x₁ i x₂:

 x0 := x1 + 0;
 LOOP ${\displaystyle x_{2}}$ DO
      ${\displaystyle x_{1}}$ := ${\displaystyle x_{1}}$ + 1
 END

W symulacji mnożenia x₀ := x₁ * x₂ można posłużyć się powyżej podaną operacją dodawania:

 x0 := 0;
 LOOP ${\displaystyle x_{2}}$ DO
      ${\displaystyle x_{0}}$ := ${\displaystyle x_{0}}$ + ${\displaystyle x_{1}}$
 END

Przykładowa instrukcja IF ${\displaystyle x_{0}}$ = 0 THEN ${\displaystyle Q}$ END może zostać przedstawiona jako poniższy program LOOP:

 x1 := 1;
 LOOP x0 DO
      x1 := 0
 END;
 LOOP x1 DO
      ${\displaystyle Q}$
 END

W symulacji tej funkcji można użyć powyżej podanej operacji mnożenia oraz instrukcji IF-THEN. Poniższy program oblicza WYKŁ(x₁, x₂) = ${\displaystyle x_{2}^{x_{1}},}$ przy czym wynik obliczenia znajduje się w zmiennej x₀:

 x0 := x1 - 1;
 IF x1 = 0 THEN x2 := 1 END;
 LOOP x0 DO x2 := x2 * x2 END;
 x0 := x2

Każdy program LOOP postaci

 LOOP ${\displaystyle x}$ DO ${\displaystyle P}$ END

może zostać zastąpiony odpowiednim programem WHILE:

 y := x + 0;
 WHILE ${\displaystyle y}$ != ${\displaystyle 0}$ DO
         ${\displaystyle y}$ := ${\displaystyle y-1;}$
         ${\displaystyle P}$
 END

pod warunkiem, że zmienna ${\displaystyle y}$ nie występuje w programie ${\displaystyle P.}$

• program GOTO
• program WHILE

• Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, 2001. ISBN 3-8274-1099-1.