Program LOOP – jedno z narzędzi teorii obliczalności służące do ustanowienia, czy dana funkcja jest obliczalna.

Cechy Programy LOOP jako model są znacznie ograniczone w możliwościach przedstawiania funkcji. (zobacz: składnia) Liczba funkcji obliczalnych za pomocą LOOP jest mniejsza niż liczba funkcji obliczalnych za pomocą maszyny Turinga. Przykładem funkcji obliczalnej za pomocą maszyny Turinga, a której nie da się przedstawić za pomocą LOOP jest funkcja Ackermanna. Programy LOOP przedstawiają funkcje totalne.

Formalna definicja Składnia Programy LOOP składają się z symboli: LOOP, DO, END, +, -, :=, ; oraz dowolnej liczby zmiennych i stałych, przy czym stałe są elementami zbioru liczb naturalnych.

Program P jest syntaktycznie zdefiniowany w notacji BNF jako:

gdzie: – stała, – zmienne, – programy LOOP.

Semantyka Wszystkie użyte w danym programie zmienne zostają zainicjalizowane przed wykonaniem programu. Zmienne nie zainicjalizowane bezpośrednio otrzymują domyślną wartość 0.

Wyrażenie postaci

xi := xj + c

oznacza przyznanie zmiennej wartości otrzymanej poprzez dodanie zmiennej i stałej Specjalnym przypadkiem jest tutaj sytuacja, gdzie wartość stałej jest równa zeru.