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:
gdzie: – stała, – zmienne, – 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 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 Dodawanie Następujący program LOOP przyznaje zmiennej x0 sumę zmiennych x1 i x2:
x0 := x1 + 0; LOOP DO := + 1 END
Mnożenie 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 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 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 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ż program GOTO program WHILE
Bibliografia
Kategoria:Teoria obliczeń