Program LOOP

Szablon:Spis treści Program LOOP – 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{matrix} P & : : = & x_{i} : = x_{j} + c \\ | & x_{i} : = x_{j} - c \\ | & P_{1}; P_{2} \\ | & L O O P x_{i} D O P E N D \end{matrix}

gdzie:

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

Semantyka

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

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

Funkcja wykładnicza

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₂) = $x_{2}^{x_{1}},$ przy czym wynik obliczenia znajduje się w zmiennej x₀:

 x₀ := x₁ - 1;
 IF x₁ = 0 THEN x₂ := 1 END;
 LOOP x₀ DO x₂ := x₂ * x₂ END;
 x₀ := x₂

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 .$

Zobacz też

Bibliografia

Szablon:Cytuj książkę