Математическая энциклопедия - универсальный нормальный алгорифм

нормальный алгорифм (н. а.) к-рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1, . .., а п}.Н. а. в алфавите (. не содержит букв является универсальным для алфавита А, если для всякого н. а. в алфавите Аи для каждого слова Рв алфавите А

Здесь есть изображение н. а. (см. Алгоритма изображение), а символ из . играет роль разделительного знака. Существование У. н. а. доказал А. А. Марков (см. [1]). Важной характеристикой У. н. а. является его сложность, т. е. длина его изображения (см. также Алгоритма сложность описания). Для минимальной сложности У. н. а. как функции от п(количества символов в алфавите А) получены отличающиеся лишь на аддитивную константу нижняя и верхняя оценки вида 5n+С(см. [2]).

Лит.:[1] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. Матем. ин-та АН СССР, т. 42); [2] Жаров В. Г., О сложности универсального нормального алгорифма, в сб.: Теория алгорифмов и математическая логика, М., 1974, с. 34-54.

С. Н. Артемов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985