Неперечислимость арифметических истин

Используя бета-функцию Гёделя, для машины Минского можно написать формулу в формальной арифметике, которая выражает тот факт, что машина Минского нс останавливается на пустом входе (начальные значения всех регистров нулевые).

Достаточно рассмотреть машины Минского с четырьмя регистрами (напомним, что такого количества регистров достаточно для моделирования машин Тьюринга).

Работа такой машины Минского М полностью описывается пятью последовательностями натуральных чисел: номерами исполняемых команд и состояниями регистров. Таким образом, нужная нам формула имеет вид.

где формула Fm выражает тот факт, что последовательности Xj, i = 1,…, 5, j = 1 кодируемые тройками.

(а*,&г, п), корректно описывают работу машины Минского М на t шагах вычисления, начиная с пустого входа, и при этом машина не останавливается за t шагов. Как видно из этого описания, формула Fj имеет вид.

Формула F выражает корректность начальных условий: исполняется первая команда и значения всех регистров нулевые. Формула F-2 описывает изменение состояния машины Минского на шаге г, т. е. связывает и Наконец, последняя формула выражает тот факт, что команда с номером t не является командой halt .

Идея построения этих формул понятна, если использовать следующее описание машины Минского. Пусть команды машины Минского и регистры нумеруются положительными числами. Тогда машина Минского описывается набором пятёрок вида (n, c, i, j, k), где п — номер команды, с? {1,2,3} — её тип, а i, j, к являются параметрами этой команды, дополненными при необходимости нулями. Итак, арифметическое описание машины Минского является набором из 5# чисел, где q — число команд. Мы считаем, что эти числа являются параметрами в формуле Тд/.

Задача 4.31. Докажите, что множество формул вида (4.39), в которых параметры описания машины Минского заменены на замкнутые термы вида г/(г/(… (0)…)), разрешимо.

Предположим, что перечислимо множество формул формальной арифметики, истинных в стандартной интерпретации.

По следствию 4.69 и задаче 4.31 перечислимо и пересечение этого множества с множеством формул вида (4.39), в которые вместо параметров описания машины Минского подставлены замкнутые термы вида i/(i/(.. (0)…)).

Но такое пересечение выделяет в точности формулы вида (4.39) для машин Минского, не останавливающихся на пустом входе. Поскольку по формуле можно восстановить машину Минского, то перечислимым оказывается и множество машин Минского, которые не останавливаются на пустом входе, что противоречит следствию 4.73.

Из полученного противоречия следует Теорема 4.80 (Тарский). Множество формул формальной арифметики, истинных в стандартной интерпретации, неперечислимо.

Если учесть, что аксиомы и правила вывода формальной арифметики разрешимы, то как следствие из теорем 4.70 и 4.80 получаем одну из форм знаменитой теоремы Гёделя о неполноте.

Следствие 4.81 (Гёдель). Формальная арифметика неполна.

Замечание 4.82. Напомним, что мы предполагаем непротиворечивость стандартной интерпретации арифметики. Таким образом, мы доказали довольно слабое утверждение. Оказывается, справедлив более сильный, чисто синтаксический, факт — формальная арифметика либо противоречива, либо неполна. Для его доказательства необходимо построить выводы в формальной арифметике для всех содержательных утверждений, которыми мы пользовались в нашем рассуждении.

Замечание 4.83. Описанный подход к доказательству теоремы Гёделя был предложен А. Н. Колмогоровым (см. [17]).

Задачи.

• 4.32. Разрешима ли алгоритмическая проблема остановки машины Тьюринга М на входе ги, если алфавит машины состоит из одного символа?
• 4.33. Покажите, что любая модель вычислений, в которой результат вычисления определён для любого входа, не является универсальной (т. е. существует алгоритм, который нельзя реализовать в этой модели).
• 4.34. Функция /: N —> N неубывающая. Верно ли, что / вычислима на машине Тьюринга?
• 4.35. Функция /: N —> N невозрастающая. Верно ли, что / вычислима на машине Тьюринга?
• 4.36. Верно ли, что для всякой всюду определённой функции /: N —> {0,1} существует машина Тьюринга, результат работы которой на входе п совпадает с /(п) для бесконечно многих п?
• 4.37. («Машины Тьюринга с односторонней лентой»). Определение такой МТ отличается от нашего основного определения лишь тем, что лента машины ограничена слева и работа всегда начинается в самой левой ячейке. Сам процесс работы не отличается от стандартного за исключением дополнительного правила остановки: если машина пытается сдвинуться влево в самой левой ячейке, то она останавливается.

Докажите, что проблема остановки МТ с односторонней лентой алгоритмически неразрешима.

• 4.38. Существует ли алгоритм, который по описанию МТ М и её входа w проверяет, что на входе w головка М хотя бы один раз возвращается в первую ячейку?
• 4.39. Существует ли алгоритм, который по описанию МТ М и её входа w проверяет, что на входе w машина М не меняет состояние ленты?
• 4.40. Существует ли алгоритм, который по описанию МТ М и её входа w проверяет, что на входе w машина. М изменяет хотя бы раз символы в ячейках, не содержащих символов входного слова w?
• 4.41. Существует ли алгоритм, который по описанию МТ М и её входа w проверяет, что на входе w головка М побывает над не более чем 2|гг| ячейками памяти? (|г^| — длина слова гг.)
• 4.42. Функция и (М) равна 1, если машина Тьюринга М на любом входном слове работает не более 1000 тактов, в противном случае и (М) = 0. Существует ли алгоритм, который по описанию М находит значение функции и{М)1
• 4.43. Функция и (М) равна количеству тех слов длины 10, на которых машина Тьюринга М не останавливается. Вычислима ли функция и (М) на машине Тьюринга?
• 4.44. Функция и (М) равна 1, если головка машины Тьюринга М на любом входном слове движется только вправо, в противном случае и (М) = 0. Существует ли алгоритм, который по описанию М находит значение функции и (М)?
• 4.45. Пусть Т (М, гг) — номер того такта работы машины Тьюринга М на входе гг, на котором головка в последний раз оказывается над пустым символом. (Если головка никогда не оказывается над пустым символом или оказывается над ним бесконечно много раз, Т (М, гг) не определена.) Вычислима ли функция Т (М, гг) на машине Тьюринга?
• 4.46. Пусть Т (М, гг) — номер того такта работы машины Тыориига М на входе гг, на котором головка в первый раз оказывается над непустым символом алфавита а. (Если головка никогда не оказывается над символом а, Т (М, гг) не определена.) Вычислима ли функция Т (М, гг) на машине Тьюринга?
• 4.47. Пусть T (M, q) — номер того такта работы машины Тьюринга М на пустом входе, после которого состояние машины в первый раз оказывается равно q. (Если машина никогда не переходит в состояние q, то T (M, q) = 0.) Вычислима ли функция T (M, q) на. машине Тыориига?
• 4.48. Приведите пример такой функции от двух переменных /(ж, у), что для любого и функция /(х, гг) (как функция от ж) вычислима на машине Тьюринга, а функция f (u, y) (как функция от у) невычислима. (Значения функции и зна-

чения переменных — слова в алфавите {0,1}.).

• 4.49. Назовем рекордом-минимумом функции /: N —> N такое число А, что f (s) = /с, а при всех t < s выполняется f (t) > f (s) = к. Обозначим Recmin/(x) функцию, которая равна 1, если х — рекорд-минимум /, а иначе равна 0. Докажите, что Recminy вычислима.
• 4.50. Назовем рекордом-максимумом функции /: N —> N такое число А, что f (s) = А, а при всех t < s выполняется f (t) < f (.s) = к. Обозначим Recmaх/(ж) функцию, которая равна 1, если х — рекорд-максимум /, и 0 в противном случае. Существует ли такая вычислимая функция /, что Recmaх/ иевычислима?
• 4.51. Существует ли алгоритм, который, но описаниям двух машин Тыоринга М. М2 проверяет истинность утверждения «машины М и М2 на любом входном слове w порождают одинаковую последовательность конфигураций»?
• 4.52. («Машины Тьюринга с хрупкой лентой») Эго машины Тьюринга со следующим ограничением: если машина меняет состояние одной из ячеек ленты второй раз, то она останавливается («лента рвётся»). Докажите, что проблема остановки машины Тыоринга с хрупкой лентой алгоритмически неразрешима.
• 4.53. Верно ли, что для всякой машины Тыоринга М существует такая машина Тьюринга М', что для любого входного слова х справедливы утверждения:
  • а) если М останавливается на х, то М' не останавливается на х
  • б) если М не останавливается на х, то М' останавливается на х?