Ученые записки математических кафедр вып. 1970 г.

- 2 6 6 ' слова А на слово А, получим: М ' ^ В У а В"В'п'П1а В " В ' п'а.В"В1П\ . . В"IV" . В последнем слове € (В "в 'п,п')< I (В"В'"') , (так как 1(А") > I (В") ) . Значит, через конечное число шагов либо зацеплений вида у первого выделенного вхождения буквы о- не будет, либо первое и второе выделенные вхождения буквы сблизятся так, что длина подслова между ними станет меньше £ (А") Следовательно, нормальный алгоритм будет применяться ко второму вхождению буквы Я- , Через конечное число шагов нормальный алго­ ритм дойдет до части слова V/ , не содержащей вхождений буквы Я. . г Теорема доказана. Простой пример показывает, что если отказаться от условия 2, то теорема неверна. Пуоть нормальный алгоритм а алфавите { л ,&} задается схемой: , ¿ а — » 4> (<) Легко видеть, что к слову И л . нормальный алгоритм (А) нм применим. Автор благодарит Грннддингера Н .Д ., под руководством которого бнда выполнена ота работа. ЛИТЕРАТУРА 1. А.А.Парков. Теория алгоритмов. Тр.матем .*н-та АН СССР, т .* 2 '; 195*.' * 2. А.И. Мальцев. Алгоритмы м рекурсивные функции. Наука,' 1965. \