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]

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

Składnia[edytuj]

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:

gdzie:

  • jest stałą,
  • , są zmiennymi
  • , to programy LOOP

Semantyka[edytuj]

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 wartości otrzymanej poprzez dodanie zmiennej i stałej . Specjalnym przypadkiem jest tutaj sytuacja, gdzie wartość stałej jest równa zeru. Wtedy wartość zmiennej zostaje bezpośrednio przyznana zmiennej :

 xi := xj + 0

Wyrażenie postaci

 xi := xj - c

oznacza przyznanie zmiennej wartości otrzymanej poprzez odjęcie stałej od zmiennej . w przypadku gdy wartość stałej jest wyższa niż wartość zmiennej wynikiem odejmowania jest 0.

Kompozycja dwóch programów LOOP ma postać

 ; 

i oznacza, że program zostanie wykonany przed programem .

Pętla LOOP ma postać

 LOOP  DO  END

przy czym liczba przebiegów programu jest z góry ustalona w zmiennej i nie ulega zmianie w trakcie wykonywania programu.

Przykładowe implementacje[edytuj]

Dodawanie[edytuj]

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

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

Mnożenie[edytuj]

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

 x0 := 0;
 LOOP  DO 
       :=  + 
 END

Symulacja instrukcji IF-THEN[edytuj]

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

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

Funkcja wykładnicza[edytuj]

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) = , 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]

Każdy program LOOP postaci

 LOOP  DO  END

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

 y := x + 0;
 WHILE  !=  DO 
          := ;
         
 END

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


Zobacz też[edytuj]

Bibliografia[edytuj]

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