Указанное выше свойство характерно и для программ, в которых один раз вычисленное значение выражения можно использовать неоднократно. Рассмотрим один из простейших классов программ - линейные или неветвящиеся программы. Такие программы представляют последовательности присваиваний вида:
где X, X1, … , Xk - переменные, F - имя k-местной базисной функции.
В случае нашего базиса B0={
Линейная программа P с выделенными входными переменными X1, … , Xn
порождает для каждого набора ?1, …, ?n значений входных переменных естественный процесс вычисления: вначале переменным X1, … , Xn присваиваются значения ?1, …, ?n, соответственно, а каждой из остальных переменных присваивается значение 0. Затем последовательно выполняются присваивания программы P, в результате чего каждая из переменных Z программы получит заключительное значение PZ(?1, …, ?n).
Определение 2.6.
Скажем, что программа P со входными переменными X1, … , Xn
вычисляет в выходной переменной Z функцию F(X1, …, Xn), если для любого набора значений входов ?1, …, ?n после завершения работы PZ(?1, …, ?n)=F(?1, …, ?n) .
Между схемами и линейными программами имеется тесная связь.
Теорема 2.1.
Доказательство. (1) Пусть S - схема со входами x1, … , xn и функциональными элементами v1, …, vm. Построим по ней линейную программу PS со входными переменными x1, … , xn следующим образом. Упорядочим все входные и функциональные вершины S по глубине (вершины одной глубины в любом порядке): u1, …, un+m.