Алгоритма Изображение

Конструктивный объект определенного вида (как правило, натуральное число или слово), содержащий в себе закодированную по фиксированным для алгоритмов данного типа правилам полную информацию об этом алгоритме. Обычно определение А. и. формулируется таким образом, чтобы процедуры получения А. и. по исходному алгоритму и восстановления исходного алгоритма по А. и. осуществлялись по возможности более просто. Изображение нормального алгорифма в алфавите А(не содержащем букв ) определяется как слово в алфавите , получаемое следующим образом (см. [1], с. 163). В каждой формуле подстановки схемы стрелка заменяется буквой , точка (если она имеется) — буквой , а в конце так построенного слова приписывается буква . Затем полученные слова выписываются друг за другом в том порядке, в каком соответствующие им формулы подстановки шли в схеме . По существу, представляет собой всего лишь несколько иначе — в виде слова — записанную схему нормального алгорифма . По соображениям, связанным с технич. деталями определения нормального алгорифма, несколько более удобным оказывается другой тип изображения нормального алгорифма — так называемая запись нормального алгорифма (см. [1], с. 187), являющаяся результатом перевода слова в к.-л. двухбуквенный алфавит (обычно 01). Аналогичным образом может быть построено изображение программы Тьюринга машины. Роль изображения рекурсивной функции играет гёделев номер системы определяющих эту функцию равенств (см. [2], с. 221). При к.-л. уточнении общего понятия алгоритма А. и. определяется с таким расчетом, чтобы оно (фактически- изображаемый им алгоритм) могло входить в состав исходных данных для алгоритмов такого типа. При этом открывается возможность доказывать так наз. "теоремы об универсальных алгоритмах", трактующие об осуществимости алгоритмов, способных моделировать по А. п. работу любого алгоритма рассматриваемого типа. Если для к.-л. алгоритма А. и. является допустимым исходным данным, то этот алгоритм наз. самоприменимым, если он применим к своему А. и., и несамоприменимым- в противном случае. Рассуждением, представляющим собой вариант "парадокса Рассела" (см. Антиномия).применительно к данной ситуации, можно показать, что естественно возникающая при этом алгоритмич. проблема распознавания самоприменимых алгоритмов среди прочих алгоритмов того же типа оказывается неразрешимой. Этот результат лежит в основе многих теорем о неразрешимости алгоритмич. проблем. Длина А. и. является одной из естественных мер алгоритма сложности (объем памяти, требующейся для запоминания программы алгоритма). Лит.:[1] Марков А. А., Теория алгорифмов, М. 1954 ("Тр. матем. ин-та АН СССР", т. 42); [2] Клин и С. К., Введение в метаматематику, пер. с англ., М., 1957. Н. М. Нагорный.