Program LOOP

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Cechy[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

Składnia[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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

 xi := xj + 0

Wyrażenie postaci

 xi := xj - 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 wykonywania programu.

Przykładowe implementacje[edytuj | edytuj kod]

Dodawanie[edytuj | edytuj kod]

Następujący program LOOP przyznaje zmiennej x0 sumę zmiennych x1 i x2:

 x0 := x1 + 0;
 LOOP x_2 DO 
      x_1 := x_1 + 1 
 END

Mnożenie[edytuj | edytuj kod]

W symulacji mnożenia x0 := x1 * x2 można posłużyć się powyżej podaną operacją dodawania:

 x0 := 0;
 LOOP x_2 DO 
      x_0 := x_0 + x_1
 END

Symulacja instrukcji IF-THEN[edytuj | edytuj kod]

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

 x1 := 1;
 LOOP x0 DO
      x1 := 0 
 END;
 LOOP x1 DO
      Q
 END

Funkcja wykładnicza[edytuj | edytuj kod]

W symulacji tej funkcji można użyć powyżej podanej operacji mnożenia oraz instrukcji IF-THEN. Poniższy program oblicza WYKŁ(x1, x2) = x_2^{x_1}, przy czym wynik obliczenia znajduje się w zmiennej x0:

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

Symulacja programu LOOP za pomocą Programu WHILE[edytuj | edytuj kod]

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.


Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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