Нормальный алгоритм - Большая Энциклопедия Нефти и Газа, статья, страница 3
Если бы у вас было все, где бы вы это держали? Законы Мерфи (еще...)

Нормальный алгоритм

Cтраница 3


Проблема распознавания применимости произвольного нормального алгоритма в А к произвольному слову в А неразрешима.  [31]

Рассмотрим еще несколько простых нормальных алгоритмов.  [32]

Как мы убедились, нормальный алгоритм Маркова в алфавите W задает некоторое преобразование слов в этом алфавите. Произвольный алгоритм в алфавите отличается от нормального тем, что его список указаний либо содержит не только стандартные указания в виде формул подстановок, либо вообще их не содержит.  [33]

Рассмотрим, например, нормальный алгоритм для вычисления абсолютного значения разности двух натуральных чисел.  [34]

Словесная формулировка содержания работы нормального алгоритма может быть уточнена при помощи граф-схемы.  [35]

Неразрешимость проблемы распознавания применимости нормального алгоритма к слову в А означает отсутствие общего метода, который для любого алгоритма и любого слова в А мог бы дать интересующий нас ответ. Ограничивая класс алгоритмов или класс обследуемых слов, или и то и другое, можно в некоторых случаях получить разрешимые массовые проблемы.  [36]

Очень важное значение для нормальных алгоритмов, как и для всякой универсальной алгоритмической системы, имеет за дача построения так называемого универсального алгоритма. Рассмотрим универсальный алгоритм применительно к нормальным алгоритмам.  [37]

С, которые заданы нормальным алгоритмом.  [38]

Для построения универсальной программы реализации нормальных алгоритмов на ЦАМ нужно построить программу перехода от одной формулы подстановки к следующей формуле подстановки. Эта программа очень проста.  [39]

Справедлива следующая теорема Маркова об универсальном нормальном алгоритме.  [40]

Понятие нормальной модели вычислений обобщает как нормальные алгоритмы, так и машины Тьюринга. Подробно об этих понятиях см., например, [ Sa ], Гл. В широком смысле, р 6 Р - список подстановок алгоритма Маркова или таблица, определяющая работу машины Тьюринга. Тогда миры С /, /, F состоят из разных слов в рабочем алфавите.  [41]

Для доказательства, достаточно сравнить определение нормального алгоритма с определением алгоритма Тьюринга при помощи программы подстановок. В самом деле, пусть F ( p) - произвольная, частично рекурсивная словарная функция, заданная в.  [42]

Докажем, что алгоритм распознавания несамопримени-мости нормальных алгоритмов невозможен. Для этого предположим, что такой алгоритм существует.  [43]

Употребляемое в формулировке принципа нормализации понятие нормального алгоритма над алфавитом означает следующее. В ряде случаев не удается построить нормальный алгоритм, эквивалентный данному алгоритму ( в алфавите А), если использовать в подстановках алгоритма только буквы алфавита А. Однако можно построить требуемый нормальный алгоритм, добавляя к алфавиту А некоторое количество новых букв или, как обычно говорят, производя расширение алфавита А. В этом случае принято говорить, что построенный ( нормальный) алгоритм является алгоритмом над алфавитом А.  [44]

Справедливо обратное: машина Тьюринга моделируется нормальным алгоритмом в алфавите, состоящем из внешнего алфавита и алфавита состояний.  [45]



Страницы:      1    2    3    4