ОПРЕДЕЛЕНИЕ. Выводом в системе Поста P = (A, B, V, P) называется всякая последовательность слов в алфавите A È B

Выводом в системе Поста P = (A, B, V, P) называется всякая последовательность слов в алфавите A È B, каждый элемент которой либо является применением одной из аксиом из P, либо получается применением одной из продукций множества P к словам, которые уже вошли в вывод.

Слово Î A* называется выводимым в системе Поста P, если в этой системе можно определить вывод, содержащий .

Множество всех слов, выводимых в системе P, обозначается как .

Длиной вывода называется число входящих в него слов.

В системах Поста возможны как конечные, так и бесконечные выводы.

Выводы в системах Поста можно рассматривать как аналог вычислений, выполняемых традиционными программами.

При этом понятие вывода является недетерминированным, поскольку в нем отсутствует условие единственности действия, которое может быть выполнено на каждом очередном шаге.

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