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}{ccc}P& ::=& M_1:I_1;M_2:I_2;...;M_k:I_k\end{array}$

Instrukcja I jest zdefiniowana jako:

$\begin{array}{ccc}I& ::=& x_i:=x_j+c\\ & |& x_i:=x_j-c\\ & |& \mathrm{G}\mathrm{O}\mathrm{T}\mathrm{O}{M}_i\\ & |& \mathrm{I}\mathrm{F}{x}_i=c\mathrm{T}\mathrm{H}\mathrm{E}\mathrm{N}\mathrm{G}\mathrm{O}\mathrm{T}\mathrm{O}{M}_i\\ & |& \mathrm{H}\mathrm{A}\mathrm{L}\mathrm{T}\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

• Szablon:Cytuj książkę