Program LOOP

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

Cechy

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.

Formalna definicja

Składnia

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:

{\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:

$c$ jest stałą,
$x_{i}$ , $x_{j}$ są zmiennymi
$P_{1}$ , $P_{2}$ to programy LOOP

Semantyka

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

Wyrażenie postaci

 x_i := x_j + c

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

 x_i := x_j + 0

Wyrażenie postaci

 x_i := x_j - c

oznacza przyznanie zmiennej $x_{i}$ wartości otrzymanej poprzez odjęcie stałej $c$ od zmiennej $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ć

  $P_{1}$ ;  $P_{2}$

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

Pętla LOOP ma postać

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

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

Przykładowe implementacje

Dodawanie

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

 x₀ := x₁ + 0;
 LOOP  $x_{2}$  DO 
       $x_{1}$  :=  $x_{1}$  + 1 
 END

Mnożenie

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

 x₀ := 0;
 LOOP  $x_{2}$  DO 
       $x_{0}$  :=  $x_{0}$  +  $x_{1}$ 
 END

Symulacja instrukcji IF-THEN

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

 x₁ := 1;
 LOOP x₀ DO
      x₁ := 0 
 END;
 LOOP x₁ DO
       $Q$ 
 END

Symulacja programu LOOP za pomocą Programu WHILE

Każdy program LOOP postaci

 LOOP  $x$  DO  $P$  END

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

 y := x + 0;
 WHILE  $y$  !=  $0$  DO 
          $y$  :=  $y-1$ ;
          $P$ 
 END

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

Bibliografia

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