|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
УНИВЕРСАЛЬНЫЙ НОРМАЛЬНЫЙ АЛГОРИФМЗначение УНИВЕРСАЛЬНЫЙ НОРМАЛЬНЫЙ АЛГОРИФМ в математической энциклопедии: нормальный алгорифм (н. а.)
Здесь Лит.:[1] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. Матем. ин-та АН СССР, т. 42); [2] Жаров В. Г., О сложности универсального нормального алгорифма, в сб.: Теория алгорифмов и математическая логика, М., 1974, с. 34-54. |
|
|
|
к-рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1, . .., а п}.Н. а. 
в алфавите 
(. не содержит букв 
является универсальным для алфавита А, если для всякого н. а. 
в алфавите Аи для каждого слова Рв алфавите А 
есть изображение н. а. (см. Алгоритма изображение), а символ 
из . играет роль разделительного знака. Существование У. н. а. доказал А. А. Марков (см. [1]). Важной характеристикой У. н. а. является его сложность, т. е. длина его изображения (см. также Алгоритма сложность описания). Для минимальной сложности У. н. а. как функции от п(количества символов в алфавите А) получены отличающиеся лишь на аддитивную константу нижняя и верхняя оценки вида 5n+С(см. [2]).