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

Dodawanie

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

 x0 := x1 + 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:

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

 x1 := 1;
 LOOP x0 DO
      x1 := 0 
 END;
 LOOP x1 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₀:

 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

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ż

• Program WHILE
• Program GOTO

Bibliografia

Uwe Schöning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag, 2001. ISBN 3-8274-1099-1. Brak numerów stron w książce