06. Теоремы сочетания

Алгоритм (в интуитивном смысле) может быть «запрограммирован» не только в виде нормального алгорифма – выписыванием его схемы, но через определенные правила комбинации (сочетания) уже построенных нормальных алгорифмов.

Например, следующее предписание определяет точный алгоритм переработки слов в заданном алфавите:

1) применить к исходному слову нормальный алгорифм ;

2)если слово определено, то к нему применить нормальный алгорифм ;

3) результатом считать слово , если оно определено.

Это предписание не является априори нормальным алгорифмом, поскольку оно не задано единой схемой такого алгорифма, а оперирует нормальными алгорифмами, словно некоторыми «блоками». Оно определяет один из способов сочетания нормальных алгорифмов, называемый Композицией (иногда Последовательной композицией).

Оказывается, что композицию и другие сочетания нормальных алгорифмов, которые будут рассмотрены ниже, можно «запрограммировать» в виде схем нормальных алгорифмов. Теоремы о возможности построения таких схем называю

Тся Теоремами сочетания.

Мы рассмотрим в этом разделе только два способа сочетания из четырех: композицию и разветвление, так как они необходимы нам для доказательства основной теоремы. Объединение (независимое, «параллельное», применение нормальных алгорифмов ко входному слову) и повторение («моделирующее» обычный программный цикл) обсудим в отдельных публикациях. Теоремы сочетания здесь формулируются без доказательства. Для простоты считаем, что все сочетаемые нормальные алгорифмы заданы в одном и том же алфавите .

Сформулируем теорему композиции.

Теорема 2 (О композиции нормальных алгорифмов). Каковы бы ни были нормальные алгорифмы и в алфавите , может быть построен такой нормальный алгорифм над алфавитом , что для любого слова имеет место условное равенство .

Нам будет удобно дальше обозначать НА как , то есть .

Способ сочетания нормальных алгорифмов, называемый Разветвлением, задается так:

1) к исходному слову применить алгорифм ;

2) если слово существует и равно пустому слову, то к слову применить алгорифм и слово считать общим результатом;

3) если слово существует и не равно пустому слову, то к слову применить алгорифм и считать слово общим результатом;

4) если слово не определено, то не определен и общий результат.

Теорема о «программировании» разветвления нормальных алгорифмов в виде схемы некоторого нормального алгорифма называется теоремой о разветвлении и формулируется следующим образом.

Теорема 3 (О разветвлении нормальных алгорифмов). Каковы бы ни были нормальные алгорифмы и в алфавите , может быть построен алгорифм над алфавитом такой, что для любого слова выполняется следующее: 1) если то ; 2) если , то при и при .

Нормальный алгорифм , который может быть построен согласно теореме о разветвлении, будем обозначать И называть -Разветвлением алгорифмов и . Коротко этот алгорифм можно задать такой записью:

.

В программистских терминах -разветвление можно описать так:

If Then Else .

Сформулированные здесь теоремы о композиции и разветвлении будут использованы при доказательстве основного результата о неразрешимости проблемы применимости для нормальных алгорифмов.

< Предыдущая		Следующая >