Гипотеза Поста: любые более широкие (в смысле алфавита символов) формулировки набора инструкций, представления и интерпретации конкретных проблем сводимы к формулировке 1

АЛГОРИТМ

очевидно <------- гипотеза ------->

ПРОГРАММА ПОСТА ФОРМУЛИРОВКА 1

Следовательно, если гипотеза верна, то любые другие формальные определения, задающие некоторый класс алгоритмов, эквивалентны классу алгоритмов, заданных формулировкой 1 Эмиля Поста.

Алгоритмы, эквивалентные программам для машины Поста, могут служить основой для построения новых (также постовых) алгоритмов путем применения (возможно, неоднократного) следующих приемов.

1. Композиция. Пусть даны алгоритмы А и В. Их композиция определяется формулой:

P(x) = B(A(x)),

т. е. результат работы алгоритма P получается после применения алгоритма B к результатам выполнения алгоритма A.

Если А и В выражены программами для машины Поста, то для их композиции необходимо приписать программу В к программе А, увеличив в В номера всех команд и отсылки на длину программы А, и заменить в А все отсылки на STOP отсылками на первую команду программы В.

2. Альтернатива. Пусть даны алгоритмы А, В и С. Альтернатива Q определяется формулой:

если А( x) = <пустое слово>, то Q(x) = B(x),

если А( x) = <непустое слово>, то Q(x) = С(x).

Если алгоритм А неприменим к x, то и альтернатива Q неприменима к x.

3. Итерация. Пусть даны алгоритмы А и В. Итерация Р определяется формулой:

если А( x) = <пустое слово>, то P(x) = x, иначе

если А( B(x)) = <пустое слово>, то P(x) = B(x), иначе

если А( B(B(x))) = <пустое слово>, то P(x) = B(B(x)), иначе

...

Алгоритм В повторяется до тех пор, пока алгоритм А вырабатывает пустое слово.