Cтраница 3
Проблема распознавания применимости произвольного нормального алгоритма в А к произвольному слову в А неразрешима. [31]
Рассмотрим еще несколько простых нормальных алгоритмов. [32]
Как мы убедились, нормальный алгоритм Маркова в алфавите W задает некоторое преобразование слов в этом алфавите. Произвольный алгоритм в алфавите отличается от нормального тем, что его список указаний либо содержит не только стандартные указания в виде формул подстановок, либо вообще их не содержит. [33]
Рассмотрим, например, нормальный алгоритм для вычисления абсолютного значения разности двух натуральных чисел. [34]
Словесная формулировка содержания работы нормального алгоритма может быть уточнена при помощи граф-схемы. [35]
Неразрешимость проблемы распознавания применимости нормального алгоритма к слову в А означает отсутствие общего метода, который для любого алгоритма и любого слова в А мог бы дать интересующий нас ответ. Ограничивая класс алгоритмов или класс обследуемых слов, или и то и другое, можно в некоторых случаях получить разрешимые массовые проблемы. [36]
Очень важное значение для нормальных алгоритмов, как и для всякой универсальной алгоритмической системы, имеет за дача построения так называемого универсального алгоритма. Рассмотрим универсальный алгоритм применительно к нормальным алгоритмам. [37]
С, которые заданы нормальным алгоритмом. [38]
Для построения универсальной программы реализации нормальных алгоритмов на ЦАМ нужно построить программу перехода от одной формулы подстановки к следующей формуле подстановки. Эта программа очень проста. [39]
Справедлива следующая теорема Маркова об универсальном нормальном алгоритме. [40]
Понятие нормальной модели вычислений обобщает как нормальные алгоритмы, так и машины Тьюринга. Подробно об этих понятиях см., например, [ Sa ], Гл. В широком смысле, р 6 Р - список подстановок алгоритма Маркова или таблица, определяющая работу машины Тьюринга. Тогда миры С /, /, F состоят из разных слов в рабочем алфавите. [41]
Для доказательства, достаточно сравнить определение нормального алгоритма с определением алгоритма Тьюринга при помощи программы подстановок. В самом деле, пусть F ( p) - произвольная, частично рекурсивная словарная функция, заданная в. [42]
Докажем, что алгоритм распознавания несамопримени-мости нормальных алгоритмов невозможен. Для этого предположим, что такой алгоритм существует. [43]
Употребляемое в формулировке принципа нормализации понятие нормального алгоритма над алфавитом означает следующее. В ряде случаев не удается построить нормальный алгоритм, эквивалентный данному алгоритму ( в алфавите А), если использовать в подстановках алгоритма только буквы алфавита А. Однако можно построить требуемый нормальный алгоритм, добавляя к алфавиту А некоторое количество новых букв или, как обычно говорят, производя расширение алфавита А. В этом случае принято говорить, что построенный ( нормальный) алгоритм является алгоритмом над алфавитом А. [44]
Справедливо обратное: машина Тьюринга моделируется нормальным алгоритмом в алфавите, состоящем из внешнего алфавита и алфавита состояний. [45]