Lup program

Lup-programi (engl. LOOP-Programs) su programi pisani u programskom jeziku Lup (engl. LOOP, krug, petlja, ciklus) koji omogućava samo operacije sabiranja, dodele vrednosti i upotrebu petlji koje su konačne. Ova vrsta programa igra značajnu ulogu u teorijskoj informatici, a posebno u vezi sa teorijom izračunljivosti. Funkcija koja se može predstaviti Lup-programom se naziva Lup-izračunljiva a skup svih Lup-programa se označava pojmom Lup (LOOP).

Osobine

Svaka primitivno-rekurzivna funkcija je Lup-izračunljiva, i obrnuto: svaki Lup-program se može predstaviti primitivno-rekurzivnom funkcijom.

Za razliku od GOTO i WHILE programa, Lup-programi se uvek završavaju. Zbog toga je skup Lup-programa u potpunosti jedan podskup izračunljivih funkcija, a time i podskup GOTO i WHILE izračunljivih funkcija.

Jedan primer Lup-izračunljive funcije je Akermanova funkcija.

Formalni opis jezika

Lup-programe čine simboli LOOP, DO, END, :=, +, - i ; kao i jedan konačan skup konstanti. Lup-programi se u Bakus-Naurovoj formi mogu prikazati kao:

${\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}}$

Pri čemu su {x₀, x₁, ...} promenljive i c konstanta koja je još i prirodan broj.

Značenje elemenata

Dok se operacije dodeljivanja vrednosti i dve računske operacije sabiranja i oduzimanja svode na već viđeno, bitno je definisati značenje LOOP — DO — END delova programa. Naime, između rezervisanih reči LOOP i DO se nalazi konačan broj, koji određuje koliko puta će ovaj ciklus biti izvršen. Bitno je naglasiti da ciklus samo preuzima broj iz promenljive i njene eventualne izmene u samom ciklusu neće uticati na broj izvršenja samog ciklusa. U ciklus spada sve između reči DO i END.

Primeri

Izračunavanje rezultata množenja x₀ · x₁:

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

Izračunavanje x₁-og stepena broja 3:

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

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

Izračunavanje vrednosti x₁-og elementa fibonačijevog niza:

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

Literatura i izvori

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