Program GOTO to jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.
Cechy Klasa funkcji obliczalnych za pomocą GOTO odpowiada klasie funkcji obliczalnych za pomocą maszyny Turinga lub programów WHILE. Program GOTO, podobnie jak program WHILE, może popaść w pętlę nieskończoną. Za pomocą programu GOTO dają się przedstawić zarówno funkcje totalne, jak również funkcje częściowe.
Formalna definicja Składnia Programy GOTO składają się z symboli: GOTO, IF, THEN, HALT, Mi, =, +, -, :, ;, := oraz dowolnej liczby zmiennych i stałych.
Program P jest syntaktycznie zdefiniowany w notacji BNF jako:
Instrukcja I jest zdefiniowana jako:
gdzie: jest stałą, elementem zbioru liczb naturalnych są zmiennymi jest znacznikiem to instrukcja stopu
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
Wyrażenie postaci
xi := xj – c
oznacza przyznanie zmiennej wartości otrzymanej poprzez odjęcie stałej od zmiennej
Skok bezwarunkowy ma postać
GOTO
i oznacza, że program w miejscu, w którym ta instrukcja została umieszczona, przeskoczy do znacznika
Skok warunkowy ma postać
IF THEN GOTO
i oznacza przeskok do znacznika w programie jeśli warunek znajdujący się za symbolem jest spełniony.
Instrukcja stopu:
HALT
stoi na końcu programu GOTO.
Symulacja za pomocą programu WHILE Program GOTO M1: A1; M2: A2; ... Mk: Ak można zasymulować za pomocą programu WHILE o następującej formie counter := 1; WHILE counter != 0 DO IF counter = 1 THEN B1 END; IF counter = 2 THEN B2 END; ... IF counter = k THEN Bk END; END Gdzie Bi = xj := xn + c; counter := counter + 1 jeśli Ai = xj := xn + c Bi = xj := xn – c; counter := counter + 1 jeśli Ai = xj := xn – c Bi = counter := n jeśli Ai = GOTO Mn Bi = IF xj = c THEN counter = n ELSE counter = counter + 1 jeśli Ai = IF xj = c THEN GOTO Mn END Bi = counter := 0 jeśli Ai = STOP
Zobacz też program LOOP program WHILE
Bibliografia
Kategoria:Teoria obliczeń