Program WHILE to jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.
Cechy Klasa funkcji obliczalnych za pomocą WHILE odpowiada klasie funkcji obliczalnych za pomocą maszyny Turinga lub programów GOTO. Programy WHILE bazują syntaktycznie i semantycznie, z wyjątkiem pętli WHILE, na programach LOOP.
Formalna definicja Składnia Programy WHILE składają się z symboli: WHILE, 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 WHILE
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 WHILE ma postać
i oznacza, że program zostanie wykonany przed programem
Pętla WHILE ma postać
WHILE DO END
przy czym liczba przebiegów programu, w przeciwieństwie do programów LOOP, nie jest z góry ustalona w zmiennej lecz może ulegać zmianom dynamicznie podczas wykonywania programu.
Przykładowa implementacja Dodawanie Następujący program WHILE przyznaje zmiennej x0 sumę zmiennych x1 i x2:
x0 := x1 + 0; y := x2 + 0; WHILE DO
= + 1 END
Symulacja pętli WHILE za pomocą programu GOTO Pętlę postaci
WHILE x 0 DO P END
można przedstawić za pomocą następującego programu GOTO:
M1: IF x = 0 THEN GOTO M2; P; GOTO M1; M2: ...
gdzie instrukcje za znacznikiem M2 są dowolne.
Zobacz też program GOTO program LOOP
Bibliografia
Kategoria:Teoria obliczeń