Program GOTO

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

Cechy[edytuj | edytuj kod]

Formalna definicja[edytuj | edytuj kod]

Składnia[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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