Математическая энциклопедия - универсальный нормальный алгорифм
Связанные словари
Универсальный нормальный алгорифм
нормальный алгорифм (н. а.) к-рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1, . .., а п}.Н. а. в алфавите (. не содержит букв является универсальным для алфавита А, если для всякого н. а. в алфавите Аи для каждого слова Рв алфавите А
Здесь есть изображение н. а. (см. Алгоритма изображение), а символ из . играет роль разделительного знака. Существование У. н. а. доказал А. А. Марков (см. [1]). Важной характеристикой У. н. а. является его сложность, т. е. длина его изображения (см. также Алгоритма сложность описания). Для минимальной сложности У. н. а. как функции от п(количества символов в алфавите А) получены отличающиеся лишь на аддитивную константу нижняя и верхняя оценки вида 5n+С(см. [2]).
Лит.:[1] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр. Матем. ин-та АН СССР, т. 42); [2] Жаров В. Г., О сложности универсального нормального алгорифма, в сб.: Теория алгорифмов и математическая логика, М., 1974, с. 34-54.
С. Н. Артемов.
Математическая энциклопедия. — М.: Советская энциклопедия
И. М. Виноградов
1977—1985
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 552 | |
2 | 479 | |
3 | 475 | |
4 | 469 | |
5 | 451 | |
6 | 435 | |
7 | 434 | |
8 | 430 | |
9 | 420 | |
10 | 420 | |
11 | 418 | |
12 | 410 | |
13 | 401 | |
14 | 373 | |
15 | 371 | |
16 | 368 | |
17 | 362 | |
18 | 360 | |
19 | 360 | |
20 | 359 |