Луп програм
Луп-програми (енгл. LOOP-Programs) су програми писани у програмском језику Луп (енгл. LOOP, круг, петља, циклус) који омогућава само операције сабирања, доделе вредности и употребу петљи које су коначне. Ова врста програма игра значајну улогу у теоријској информатици, а посебно у вези са теоријом израчунљивости. Функција која се може представити Луп-програмом се назива Луп-израчунљива а скуп свих Луп-програма се означава појмом Луп (LOOP).
Особине
[уреди | уреди извор]Свака примитивно-рекурзивна функција је Луп-израчунљива, и обрнуто: сваки Луп-програм се може представити примитивно-рекурзивном функцијом.
За разлику од GOTO и WHILE програма, Луп-програми се увек завршавају. Због тога је скуп Луп-програма у потпуности један подскуп израчунљивих функција, а тиме и подскуп GOTO и WHILE израчунљивих функција.
Један пример Луп-израчунљиве фунције је Акерманова функција.
Формални опис језика
[уреди | уреди извор]Луп-програме чине симболи LOOP, DO, END, :=, +, - и ; као и један коначан скуп константи. Луп-програми се у Бакус-Науровој форми могу приказати као:
При чему су {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