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

 x_i := x_j + c

oznacza przyznanie zmiennej $x_{i}$ wartości otrzymanej poprzez dodanie zmiennej $x_{j}$ i stałej $c.$

Wyrażenie postaci

 x_i := x_j – 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ż

Bibliografia

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