Program GOTO

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, M_i, =, +, -, :, ;, := oraz dowolnej liczby zmiennych i stałych.

Program P jest syntaktycznie zdefiniowany w notacji BNF jako:

${\begin{array}{lrl}P&::=&M_{1}:I_{1};M_{2}:I_{2};...;M_{k}:I_{k}\end{array}}$

Instrukcja I jest zdefiniowana jako:

${\begin{array}{lrl}I&::=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&\mathrm {GOTO} M_{i}\\&|&\mathrm {IF} \,x_{i}=c\,\mathrm {THEN} \,\mathrm {GOTO} \,M_{i}\\&|&\mathrm {HALT} \end{array}}$

gdzie:

• $c$ jest stałą, elementem zbioru liczb naturalnych
• $x_{i},$ $x_{j}$ są zmiennymi
• $M_{i}$ jest znacznikiem
• $HALT$ 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 $x_{i}$ wartości otrzymanej poprzez dodanie zmiennej $x_{j}$ i stałej $c.$

Wyrażenie postaci

 xi := xj – c

oznacza przyznanie zmiennej $x_{i}$ wartości otrzymanej poprzez odjęcie stałej $c$ od zmiennej $x_{j}.$

Skok bezwarunkowy ma postać

 GOTO $M_{i}$

i oznacza, że program w miejscu, w którym ta instrukcja została umieszczona, przeskoczy do znacznika $M_{i}.$

Skok warunkowy ma postać

 IF $x_{i}=c$ THEN GOTO $M_{i}$

i oznacza przeskok do znacznika $M_{i}$ w programie jeśli warunek znajdujący się za symbolem $IF$ 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

• Uwe Schöning: Theoretische Informatik – kurzgefasst. Spektrum Akademischer Verlag, 2001. ISBN 3-8274-1099-1.brak strony w książce