Луп програм

Из Википедије, слободне енциклопедије

Луп-програми (енгл. 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}

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

Значење елемената[уреди]

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

Примери[уреди]

Израчунавање резултата множења x0 · x1:

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

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

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

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

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

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