Луп програм

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

Особине

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

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

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

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

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

$\begin{array}{ccc}P& ::=& x_i:=x_j+c\\ & |& x_i:=x_j-c\\ & |& P;P\\ & |& \mathrm{L}\mathrm{O}\mathrm{O}\mathrm{P}{x}_i\mathrm{D}\mathrm{O}P\mathrm{E}\mathrm{N}\mathrm{D}\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}-