Универсальный нормальный алгорифм

нормальный алгорифм (н. а.) [img: http://localhost:8080/file/052105-124.jpg] к-рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1,..., а п}.Н. а. [img: http://localhost:8080/file/052105-125.jpg] в алфавите [img: http://localhost:8080/file/052105-126.jpg] [img: http://localhost:8080/file/052105-127.jpg] (. не содержит букв [img: http://localhost:8080/file/052105-128.jpg] является универсальным для алфавита А, если для всякого н. а. [img: http://localhost:8080/file/052105-129.jpg] в алфавите Аи для каждого слова Рв алфавите А [img: http://localhost:8080/file/052105-130.jpg] Здесь [img: http://localhost:8080/file/052105-131.jpg] есть изображение н. а. (см. Алгоритма изображение), а символ [img: http://localhost:8080/file/052105-132.jpg] из. играет роль разделительного знака. Существование У. н. а. доказал А. А. Марков (см. [1]). Важной характеристикой У. н. а. является его сложность, т. е. длина его изображения (см. также Алгоритма сложность описания). Для минимальной сложности У. н. а. как функции от п(количества символов в алфавите А) получены отличающиеся лишь на аддитивную константу нижняя и верхняя оценки вида 5n+С(см. [2]).