Алгебра тьюринговых программ
Для записи программ в виде формульных выражений введем обозначения для некоторых элементарных программ и операций, позволяющие строить из уже созданных программ более сложные.
Элементарными вычисляющими программами будем называть программы вида
Обозначать их будем, соответственно, символами
где .
Программы, у которых множество выходов разбито на два непустых подмножества: подмножество да-выходов и подмножество нет-выходов, назовем бинарными распознающими программами.
Элементарными распознающими программами будем считать программы вида
Обозначать такую программу будем через .
Правила композиции. Введем несколько правил, которые позволят нам из уже построенных программ создавать более сложные.
- Если — программы, то выражение обозначает программу, которая получена следующим образом. Все выходы программы соединены дугой с входом программы . Каждая такая дуга помечена буквами из , которые не использованы на других дугах, выходящих из рассматриваемой выходной вершины (в дальнейшем при соединении выходов одной программы с входом другой будем пользоваться этим правилом). Входом в полученную программу является вход программы , а выходами — выходы программы . Таким образом, программа предписывает последовательное выполнение программ .
- Если — бинарная распознающая программа, а — произвольная, то выражение
означает программу, полученную следующим образом. Все да-выходы программы соединяются с входом программы . Входом в полученную программу является вход в программу , а выходом — выходы программы и нет-выходы программы . Программы такого вида называются охраняемыми, и в таких случаях говорят, что программа охраняется программой .
- Если дан набор охраняемых программ вида (если ) , то выражение вида
обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом ; нет-выходы программы
соединяются с входом . Входом в полученную программу является вход в программу , а выходом — выходы программ
и нет-выходы программы .
- Если — бинарная распознающая программа, а — любая, то выражение
обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом программы . Все выходы программы соединены с входом в . Входом в полученную программу является вход в , а выходом — нет-выходы программы .
- Если — бинарная распознающая программа, а — любая, то выражение
обозначает программу, полученную соединением нет-выходов программы с входом в , а выходов
— с входом в . Входом в полученную программу является вход в , а выходами — да-выходы программы .
Сокращения. Программы вида
будем сокращенно записывать в виде
а программы вида
в случае, когда — в виде .
В контексте со словами "если", "пока", "до" угловые скобки в записи элементарного распознающего оператора
будем опускать.
