Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
в) Присоединить к U машину V, уменьшающую число палочек в представлении числа f(y, хи ..., хп) = г на единицу для того, чтобы можно было распознать, равно ли это число нулю.
г) Присоединить к построенным машинам еще одну машину Wy которая в случае г Ф О прибавляла бы к у палочку и переходила бы тем самым к у + 1.
д) Присоединить к соединению построенных машин стандартную машину Y, которая при г = О очищала бы ленту от символов, отличных от |, и делала содержимое ленты равным у.
е) Убедиться, что машина, представляющая собой соединение машин Т, U, V, W и У, обладает всеми нужными свойствами.
3. Напомним, что функции (х + 1) (у + 1) и х — у вычислимы; доказательство этого предлагалось выше (см. § 4.4) в качестве упражнения. (Функция х — у получается тривиальным продолжением функции X — у, а именно х — у имеет значение либо х — у, либо нуль в зависимости от того, определено X — у или нет.)
Опираясь на вычислимость этих функций (а также на вычисление проекций, см. § 4.4), доказать, что функция ху также вычислима.
4. Доказать, что функция Xh вычислима для любого h^N.
5.2.4. Модифицированные машины Тьюринга
Можно рассмотреть различные расширения понятия машины Тьюринга. Например:
. Можно присоединить к машине Z некоторое конечное множество натуральных чисел А и множество команд Siqjquqi, означающих, что в ситуации (Si, qj) и для конфигурации а машина Z переходит либо в состояние qu, либо в состояние qi в зависимости от того, принадлежит ли содержимое (а) данной конфигурации множеству А. Такое расширение машин Тьюринга, рассмотренное Дэ-висом, не увеличивает их вычислительную мощность. .. Можно добавить к машине Тьюринга разного рода специализированные компоненты: ленту для входных данных, ленту для окончательных результатов, ленту для промежуточных вычисле- 6
Часть /. Предварительные сведения из логики и алгебры
ний, более сложные команды и т. п. Вообще говоря, нетрудно показать, что такие сложные машины эквивалентны простым машинам.
§ 5.3. МЕТОД ГЁДЕЛЯ
Мы уже имели случай заметить, что на уровне машин Тьюринга различение «численных» и «нечисленных» операций не имеет разумного оправдания.
Еще в начале 30-х годов Курт Гёдель применил числовое кодирование имен некоторых метаматематических объектов в доказательстве своей знаменитой теоремы о неполноте арифметики.
Метод Гёделя позволяет оперировать с нечисленными объектами, как с числами; программисты, для которых действия над адресами — дело привычное, сразу же поймут этот подход.
Итак, пусть имеется некоторый алфавит и цепочки из символов этого алфавита.
Каждой такой цепочке, представляющей собой нечисленный •объект, мы поставим в соответствие некоторое целое положительное число — ее гёделевский номер, обладающий следующими свойствами:
. Существует машина Тьюринга, которая для любой цепочки, написанной на ее ленте, выдает в качестве окончательного результата ее гёделевский номер.
.. Существует машина Тьюринга, которая для любого числа, написанного на ее ленте, выдает один из двух следующих ответов:
— либо «Не существует цепочки, соответствующей этому числу» (т. е. цепочки, для которой данное число являлось бы ее гёде-левским номером);
— либо «Цепочка, соответствующая этому числу, есть...».
Таким образом, гёделевский номер, сопоставленный цепочке,
полностью определяет ее; он является ее собственным именем и одновременно, будучи числом, может участвовать в вычислениях.
Аналогичным образом можно нумеровать последовательности цепочек.
5.3.1. Один из возможных способов нумерации цепочек
Говоря о машинах Тьюринга, мы используем выражения, в которых фигурируют:
символы Saqc различными индексами;
символы JI и Я.
Для записи индексов мы будем пользоваться двоичной системой счисления, причем роль цифр будут играть символы Z (zero, т. е. 'нуль') и и (ип, т. е. 'один'); будем писать индексы в строчку:
50 записывается как Sz,
51 записывается как Su, Гл. V. Вычислимость и разрешимость
87
52 записывается как Suz,
53 записывается как Suu, q5 записывается как quzu.
Если нам понадобятся последовательности цепочек, мы будем пользоваться разделительным знаком «!». Итак, мы имеем следующие символы:
(5, q, z, и, Л, П, !}.
Занумеруем цепочки, состоящие из этих символов, следующим образом.
Пустой цепочке сопоставим число 0. Цепочкам длины 1 сопоставим соответственно
S, q, z, и, Л, П, !,
1, 2, 3, 4, 5, 6, 7.
Произвольной цепочке сопоставляется число (в восьмеричной системе счисления при указанном выше кодировании цифр), которое является ее каноническим представлением.
Пример. Команда q^SbStfi, записывается как
quuSuzuSzquzz;
этому выражению соответствует восьмеричное число 2441434132433.
Мы видим, что номер цепочки определяется по ней чисто механически; стало быть, это может делать машина Тьюринга.
Если мы пойдем в обратном направлении, т. е. будем отправляться «от чисел», то увидим, что
числу 0 соответствует пустая цепочка;
восьмеричному числу, не содержащему цифры 0, соответствует единственная цепочка или единственная последовательность цепочек;
