Алгебра тьюринговых программ

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

Элементарными вычисляющими программами будем называть программы вида

Обозначать их будем, соответственно, символами

где .

Программы, у которых множество выходов разбито на два непустых подмножества: подмножество да-выходов и подмножество нет-выходов, назовем бинарными распознающими программами.

Элементарными распознающими программами будем считать программы вида

Обозначать такую программу будем через .

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

Если — программы, то выражение обозначает программу, которая получена следующим образом. Все выходы программы соединены дугой с входом программы . Каждая такая дуга помечена буквами из , которые не использованы на других дугах, выходящих из рассматриваемой выходной вершины (в дальнейшем при соединении выходов одной программы с входом другой будем пользоваться этим правилом). Входом в полученную программу является вход программы , а выходами — выходы программы . Таким образом, программа предписывает последовательное выполнение программ .
Если — бинарная распознающая программа, а — произвольная, то выражение

означает программу, полученную следующим образом. Все да-выходы программы соединяются с входом программы . Входом в полученную программу является вход в программу , а выходом — выходы программы и нет-выходы программы . Программы такого вида называются охраняемыми, и в таких случаях говорят, что программа охраняется программой .
Если дан набор охраняемых программ вида (если ) , то выражение вида

обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом ; нет-выходы программы

соединяются с входом . Входом в полученную программу является вход в программу , а выходом — выходы программ

и нет-выходы программы .
Если — бинарная распознающая программа, а — любая, то выражение

обозначает программу, полученную следующим образом. Да-выходы программы соединяются с входом программы . Все выходы программы соединены с входом в . Входом в полученную программу является вход в , а выходом — нет-выходы программы .
Если — бинарная распознающая программа, а — любая, то выражение

обозначает программу, полученную соединением нет-выходов программы с входом в , а выходов

— с входом в . Входом в полученную программу является вход в , а выходами — да-выходы программы .

Сокращения. Программы вида

будем сокращенно записывать в виде

а программы вида

в случае, когда — в виде .

В контексте со словами "если", "пока", "до" угловые скобки в записи элементарного распознающего оператора

будем опускать.

Содержание Назад Вперед