Program GOTO to jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.

• 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.

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:

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

Instrukcja I jest zdefiniowana jako:

${\displaystyle {\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:

• ${\displaystyle c}$ jest stałą, elementem zbioru liczb naturalnych
• ${\displaystyle x_{i},}$ ${\displaystyle x_{j}}$ są zmiennymi
• ${\displaystyle M_{i}}$ jest znacznikiem
• ${\displaystyle HALT}$ to instrukcja stopu

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 ${\displaystyle x_{i}}$ wartości otrzymanej poprzez dodanie zmiennej ${\displaystyle x_{j}}$ i stałej ${\displaystyle c.}$

Wyrażenie postaci

 xi := xj – c

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

Skok bezwarunkowy ma postać

 GOTO ${\displaystyle M_{i}}$

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

Skok warunkowy ma postać

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

i oznacza przeskok do znacznika ${\displaystyle M_{i}}$ w programie jeśli warunek znajdujący się za symbolem ${\displaystyle IF}$ jest spełniony.

Instrukcja stopu:

 HALT

stoi na końcu programu GOTO.

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

• program LOOP
• program WHILE

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