Неразрешимость логики первого порядка (стр. 6 из 7)

Не существует эффективной процедуры, позволяющей решать, останавливается ли произвольная машина Тьюринга Т при произвольном входном значении nи по данной машине Тьюринга Т можно построить примитивно рекурсивную функцию g, обладающую следующим свойством: какое бы n мы не взяли, g(n, t) = 0 в точности тогда, когда t– номер шага, более позднего, чем тот, на котором машина T останавливается, если ее запустить при входном значении n. (по определению функции g, если шаг tне таков, то g(x, t) = <a, b, c> =

для некоторых a, b, c и потому g(x, t) > 0. Если же t – такой шаг, то g(x, t) = 0.

Таким образом, если дана машина Т, то можно эффективно построить некоторую конечную последовательность q₀, q₁, …, q_rпримитивно рекурсивных функций, удовлетворяющую двум условиям: 1) каждая функция g_i либо является базисной функцией, либо получается из некоторых предыдущих функций с помощью композиции или примитивной рекурсии и 2) для всякого nмашина T, запущенная на входном значении n, в конце концов останавливается тогда и только тогда, когда g_r(n, t) = 0 для некоторого t.

Построим теперь по данной T последовательность примитивно рекурсивных функций, удовлетворяющую условиям 1) и 2). Каждой функции g_i поставим в соответствие свой функциональный символ g_i с тем же числом аргументов, что иg_i. Пусть g₀ = '. Используя эти символы, выпишем для каждого g_iодну или две очевидные формулы, определяющие функцию g_i Например,

если g_i= z, то "xg_i(x) = 0

еслиg_i = s, то "xg_i(x) = x'

если g_i =

, то "x₁ … "x_m … "x_ng_i(x₁, …,x_m, …,x_n) = x_m

Если g_i получается из предшествующих ей функций g_jи g_kc помощью примитивной рекурсии, то "xg_i(x, 0) =g_j(x) и "x"yg_i(x, y') =g_k(x, y, g_i(x, y))

Если же g_iполучается из предшествующих ей функций g_о и

путем композиции, то "xg_i(x) =g_j (для краткости заменили здесь x₁, x₂, …, x_nна x, a"x₁, "x₂, …, "x_nна "x)

Запишем также формулы "xx' ≠ 0 и "x"y(x' = y' → x = y). Обозначим теперь через Г множество всех этих формул, а через I – формулу

.

Утверждение. Машина T при входном значении

останавливается тогда и только тогда, когда Г ├ I.

«Тогда». Пусть Г ├ I. Обозначим через

модель, областью которой служит множество натуральных чисел и которая интерпретирует символ 0 как 0, а функциональные символы g_i – как . Все предложения из Г истинны в . Поскольку Г ├ I, предложение Iистинно также. Следовательно, для некоторого справедливо . Согласно 2), T останавливается на .

«Только тогда». Предположим, что Т останавливается при входном значении

. Для доказательства соотношения Г ├ I предположим, что – произвольная модель, в которой все предложения из Г истинны, и покажем, что из этого предположения следует истинность в . Пусть теперь – интерпретация символа 0 в модели , a – при всяком – интерпретация в символа g_i. Пусть, далее, (так что – интерпретация в символа ), и пусть . Так как формулы и истинны в , функция , для которой и , является изоморфизмом множества {0, 1, 2,…} натуральных чисел на множество N. Таким образом, можно считать, что N и является в действительности множеством натуральных чисел, , ограничение функции на множество N есть , а потому всякий нумерал е обозначает число в .

Индукцией по

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

Поскольку

при входном значении останавливается, можно утверждать, что для некоторого справедливо , откуда , а потому истинно в , а значит, и I = истинно в , и доказательство заканчивается.