Луп програм

Луп-програми (енгл. LOOP-Programs) су програми писани у програмском језику Луп (енгл. LOOP, круг, петља, циклус) који омогућава само операције сабирања, доделе вредности и употребу петљи које су коначне. Ова врста програма игра значајну улогу у теоријској информатици, а посебно у вези са теоријом израчунљивости. Функција која се може представити Луп-програмом се назива Луп-израчунљива а скуп свих Луп-програма се означава појмом Луп (LOOP).

Особине

Свака примитивно-рекурзивна функција је Луп-израчунљива, и обрнуто: сваки Луп-програм се може представити примитивно-рекурзивном функцијом.

За разлику од GOTO и WHILE програма, Луп-програми се увек завршавају. Због тога је скуп Луп-програма у потпуности један подскуп израчунљивих функција, а тиме и подскуп GOTO и WHILE израчунљивих функција.

Један пример Луп-израчунљиве фунције је Акерманова функција.

Формални опис језика

Луп-програме чине симболи LOOP, DO, END, :=, +, - и ; као и један коначан скуп константи. Луп-програми се у Бакус-Науровој форми могу приказати као:

${\begin{array}{lrl}P&::=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P;P\\&|&\mathrm {LOOP} \,x_{i}\,\mathrm {DO} \,P\,\mathrm {END} \end{array}}$

При чему су {x₀, x₁, ...} променљиве и c константа која је још и природан број.

Значење елемената

Док се операције додељивања вредности и две рачунске операције сабирања и одузимања своде на већ виђено, битно је дефинисати значење LOOP — DO — END делова програма. Наиме, између резервисаних речи LOOP и DO се налази коначан број, који одређује колико пута ће овај циклус бити извршен. Битно је нагласити да циклус само преузима број из променљиве и њене евентуалне измене у самом циклусу неће утицати на број извршења самог циклуса. У циклус спада све између речи DO и END.

Примери

Израчунавање резултата множења x₀ · x₁:

x1 := x1 - 1;
LOOP x0 DO
  LOOP x1 DO
    x0 := x0 + 1
  END
END

Израчунавање x₁-ог степена броја 3:

x0 := 0;
x0 := x0 + 1;

LOOP x1 DO
  LOOP x0 DO
    x0 := x0 + 1
    x0 := x0 + 1
  END
END

Израчунавање вредности x₁-ог елемента фибоначијевог низа:

x0 := 0;
x2 := 0;
x3 := 0;

x2 := x2 + 1;

LOOP x1 DO
  x3 := x0 + 0

  LOOP x2 DO
    x0 := x0 + 1
  END

  x2 := x3 + 0
END

Литература и извори

• Informatik 3, Prof. Dr. Peter Deussen, Universität Karlsruhe, 2001, pp. 162 — 167
• Kfoury, Moll, Arbib, A Programming Approach to Computability, Springer, 1982