Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
восьмеричному числу, содержащему хотя бы одно вхождение цифры 0, не соответствует ни одной цепочки или последовательности цепочек.
5.3.2. Гёделевский номер машины Тьюринга
Машина Тьюринга может рассматриваться как множество команд Qi, Q2, ..., Qn-
Сопоставим каждой команде ее гёделевский номер
ng(Qi), ng (Q2).....ng(Q„),
а затем расположим эти номера в порядке возрастания. (Нам даже не придется использовать разделитель 7 =• !, поскольку 1 = S и 2 = q служат маркерами.)
Таким образом каждая машина Тьюринга получит свой гёделевский номер. Поскольку процедура приписывания номеров 88
Часть /. Предварительные сведения из логики и алгебры
машинам является механической, мы можем поручить ее выполнение некоторой машине Тьюринга, которая будет обозначаться через Gi; любопытно отметить, что G1 вычисляет, в частности, и свой собственный гёделевский номер.
Обратно, существует такая машина Тьюринга G2, которая для любого восьмеричного числа выдает один из двух следующих ответов:
— либо «Это число не является гёделевским номером никакой машины Тьюринга»;
— либо «Это число является гёделевским номером машины Тьюринга, имеющей следующие команды...».
Заметим, что если G2 получает на вход свой собственный гёделевский номер, то она выдает ответ второго типа.
5.3.3. Упражнение: другой способ кодирования
В оригинальных работах Гёделя использовался следующий способ нумерации. Пусть требуется закодировать выражение
M = 'YilYi, - - • Yij /,
которое составлено из символов, принадлежащих набору
{VhY2> •••> Yft. •••}•
При этом должен быть отмечен тот факт, что символ Yft выступает на месте с номером k, т. е. мы должны кодировать и символы, и места.
. Мы будем кодировать символы, взаимно однозначно отображая их на множество нечетных чисел, больших единицы, по следующей схеме:
символы Yi: JI П S0 q{ S1 q2 S2 q$ ... числа at: 3 5 7 9 11 13 15 17 ____
.. Мы будем кодировать имена мест, взаимно однозначно отображая их на множество простых чисел, расположенных в порядке возрастания:
номера мест: 1 2 3 4 5 ... k ... простые числа: 2 3 5 7 11 ... pk ... . .... Выражению
'Yi1Yi, • •. Yi;
отвечает по определению произведение
2а'1 X 3а'' X ... X pVk X ... X рпп,
т. е. некоторое положительное целое число, которое мы обозначим через ng(Al); это и есть гёделевский номер выражения М. Полу- Гл. V. Вычислимость и разрешимость
89
ченный гёделевский номер ng(Al) допускает единственное разложение на множители, и ему отвечает единственное выражение М.
Чтобы код был полным, условимся кодировать пустое выражение целым числом 1.
Последовательности выражений. Аналогичным образом последовательность выражений
M1, M2, ..., Mj, ..., M4 кодируется посредством числа
2ng (M1) х gng (M1) х х pnS (Mj) х _ х png W
а) Закодировать команду (<7, | П q2).
б) Декодировать выражение 2173п5177и.
в) Закодировать последовательность <p = (^1 | IJq2, q3 \ Bq1).
г) Доказать, что никакое число не может быть одновременно гёделевским номером выражения и последовательности выражений. Доказать, что ng(<p) = ng(t|)) влечет за собой ф = гр. Для этого ng(<p) должно быть представлено в виде 2m- (2q +1); затем следует рассмотреть все возможные случаи в зависимости от четности т.
§ 5.4. РЕКУРСИВНЫЕ И РЕКУРСИВНО ПЕРЕЧИСЛИМЫЕ МНОЖЕСТВА
5.4.0. Функции Q?(X)
Для любого целого числа z возможны два взаимоисключающих случая:
. либо не существует никакой машины Тьюринга, имеющей z в качестве своего гёделевского номера;
.. либо такая машина существует и притом только одна. Мы будем говорить, что функция f(X),
Ж є= Np-Uf (II)C=N
частично вычислима, если для некоторой машины Тьюринга она является той функцией, которую эта машина вычисляет. Иначе говоря, всякой частично вычислимой функции /(X) можно сопоставить гёделевский номер г той машины Тьюринга, которая эту функцию вычисляет (может существовать несколько разных машин, вычисляющих одну и ту же функцию).
Теперь мы определим функции Qz(X) следующим образом. Пусть имеется пара, образованная целым неотрицательным числом Z и входным заданием X ejV. Тогда: . Если г есть гёделевский номер машины Z, вычисляющей частично вычислимую функцию /(X), то Q?(X) совпадает с /(X). 90
Часть /. Предварительные сведения из логики и алгебры
.. Если Z не является гёделевским номером никакой машины, то Qz(X) принимает значение 0. Ясно, что последовательность
QS(X), Qf(X), Qn(X), ...
перечисляет, быть может с повторениями, множество частично вычислимых функций от р аргументов. Заметим (это понадобится нам в дальнейшем), что мы умеем, таким образом, перечислять области определения частично вычислимых функций.
5.4.1. Природа функций Qz(X)
Очевидно, что Qz(X) есть функция от р + 1 аргументов с областью определения Np+i, принимающая значения из N.
Пусть заданы z и X. Тогда, чтобы вычислить значение Qz, необходимо сначала выяснить, является ли z гёделевским номером какой-либо машины Тьюринга. Этот вопрос сводится к проблеме декодирования с ответами «да»/«нет», которую мы поручали машине Тьюринга G2 (см. п. 5.3.2).
