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

122

нормальный алгорифм (н. А.) к-рый в уточненном ниже смысле моделирует работу любого н. А. В алфавите A ={a1, . .., а п}.Н. А. в алфавите (. Не содержит букв является универсальным для алфавита А, если для всякого н. А. в алфавите Аи для каждого слова Рв алфавите А Здесь есть изображение н. А. (см. Алгоритма изображение), а символ из . Играет роль разделительного знака. Существование У. Н. А. Доказал А. А. Марков (см. [1]). Важной характеристикой У. Н. А. Является его сложность, т. Е. Длина его изображения (см. Также Алгоритма сложность описания). Для минимальной сложности У. Н. А. Как функции от п(количества символов в алфавите А) получены отличающиеся лишь на аддитивную константу нижняя и верхняя оценки вида 5n+С(см. [2]). Лит.:[1] Марков А. А., Теория алгорифмов, М.-Л., 1954 (Тр.

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

Значения в других словарях
Универсальное Пространство

- топологич. Пространство, содержащее гомеоморфный образ любого топологич. Пространства нек-poгo класса. Примеры. 1) С[0,1], см. Банахово пространство. 2) гильбертов кирпич и тихоновский куб. 3) кривая Монгера (см. Линия). 4) универсальное расслоение Милнора (см. Главное расслоение). Свойство универсальности обеспечивает рассмотрение нск-рого абстрактно заданного объекта как под-объекта более простого (с категорией точки зрения) и тем самым наделяет его лвнешними. ..

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

для данного класса алгоритмов - алгоритм с входным параметром р, к-рый при различных допустимых значениях р моделирует работу любого алгоритма данного класса. Различным формализациям вычислимости соответствуют различные уточнения понятия У. А. Для рекурсивных функций это универсальная частично рекурсивная функция (см. Универсальная функция), для Тьюринга машин - это универсальная машина Тьюринга, для нормальных алгорифмов - это универсальный нормальный алгорифм, и т. Д. Лит.:[1] Успснский В..

Универсальный Ряд

- функциональный ряд с помощью к-рого могут быть представлены в том или ином смысле все функции заданного класса. Напр., существует такой ряд (1), что для каждой непрерывной на [ а, b]функции f найдется подпоследовательность частных сумм этого ряда сходящаяся к f(x)равномерно на [ а, b]. Существуют тригонометрические ряды со стремящимися к нулю коэффициентами такие, что для каждой измеримой (по Лебегу) на функции f имеется подпоследовательность частных сумм ряда (2), сходящаяся к f(х)почти..

Универсальных Алгебр Многообразие

- класс универсальных алгебр, определяемый системой тождеств (ср. Алгебраических систем многообразие). У. А. М. Характеризуется как непустой класс алгебр, замкнутый относительно факторалгебр, подалгебр и прямых произведений. Последние два условия можно заменить требованием замкнутости относительно подпрямых произведений. У. А. М. Наз. Тривиальным, если оно состоит из одноэлементных алгебр. Каждое нетривиальное У. А. М. Содержит свободную алгебру с базой любой мощности. Если X и Y - базы одной и..

Дополнительный поиск Универсальный Нормальный Алгорифм Универсальный Нормальный Алгорифм

Добавить комментарий
Комментарии
Комментариев пока нет

На нашем сайте Вы найдете значение "Универсальный Нормальный Алгорифм" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Универсальный Нормальный Алгорифм, различные варианты толкований, скрытый смысл.

Первая буква "У". Общая длина 33 символа