Xreferat.com » Рефераты по математике » Неразрешимость логики первого порядка

Неразрешимость логики первого порядка

t' An y)))


(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х + 1, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)

Аналогично для строк вида qi aj → aj Л qk включаем в Д


"x "y "t ((t Qi x' Неразрешимость логики первого порядка t Aj x') → (t' Qk x Неразрешимость логики первого порядка (t A0 y → t' A0 y) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка (t An y → t' An y)))


(«Если в момент времени t машина находится в состоянии qi, считывая при этом символ aj в клетке х + 1, то в момент t + 1 машина перейдет в состояние qk, считывая при этом клетку х, и во всех клетках в момент t + 1 останутся те же символы, что в момент t для всех t и х.»)

Одно из предложений множества Д утверждает, что в начальный момент машина находится в состоянии q1, считывая при этом самую левую единицу в сплошном массиве единиц на ленте с пустыми символами в остальных клетках:


0 Qi 0 Неразрешимость логики первого порядка 0 A1 0 Неразрешимость логики первого порядка 0 A1 0' Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0 A1 0(n-1) Неразрешимость логики первого порядка "y ((y ≠ 0 Неразрешимость логики первого порядка y ≠ 0' Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y ≠ 0(n-1)) → 0 A0 y)


Здесь 0(n-1) обозначает результат применения n символов следования к символу 0.

Еще одна из формула множества Д утверждает, что всякое целое число является следующим точно за одним целым:


"z $x z = x' Неразрешимость логики первого порядка "z "x "y (z = x' Неразрешимость логики первого порядка z = y' → x = y)


Введем в Д еще одну формулу


"x "y "z (x < y Неразрешимость логики первого порядка y < z → x < z) Неразрешимость логики первого порядка "x "y (x' = y → x < y) Неразрешимость логики первого порядка "x "y (x < y → x ≠ y),


из которого следует, что если p и q – различные натуральные числа, то "x x(p) ≠ x(q).

Таким образом, Д состоит из формул (1), (2), (3), соответствующих всем командам машины, и трема дополнительными (4), (5), (6). Что касается предложения Н, то заметим, что всякая машина останавливается в момент времени t, если она в это время находится в состоянии qi, считывая при этом символ aj, причем в машинной таблице нет команды, соответствующей комбинации qi aj. Таким образом, за предложение Н мы принимаем дизъюнкцию всех предложений вида

$t $x (t Qi x Неразрешимость логики первого порядка t Ai x),


для которых в машинной таблице нет команд, соответствующих комбинациям qiaj. Если же для всякой такой комбинации в таблице имеются команды, то машина никогда не остановится, и за Н в этом случае мы принимаем какую-либо формулу, ложную в интерпретации I, например 0 ≠ 0.

Мы показали, как по данной машине и входному значению n построить такие конечное множество предложений Д и отдельное предложение Н, что соотношение Д ├ Н имеет место тогда и только тогда, когда машина, получив n на входе, в конце концов, останавливается.

Рассмотрим факты, касающиеся отношения ├ в логике первого порядка. Все предложения из множества Д истинны в интерпретации I. Поэтому если Д ├ Н, то и Н истинно в I. Но Н истинно в I тогда и только тогда, когда машина, получив на входе n, в конце концов останавливается.

Введем теперь один специальный тип формул, называемых нами описаниями времени s. Так называется всякая формула, определяющая очевидным способом, в каком состоянии находится машина в момент s, какая клетка ею в это время считывается, а также в каких клетках ленты какие символы записаны, причем все это делается на языке множества формул Д Неразрешимость логики первого порядка {Н}. Точнее говоря, всякое описание времени s есть формула вида


0(s)Qi0(p) Неразрешимость логики первого порядка 0(s)Неразрешимость логики первого порядка Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s)Aj0(p) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s)Неразрешимость логики первого порядка Неразрешимость логики первого порядка "y ((y Неразрешимость логики первого порядка Неразрешимость логики первого порядка Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y Неразрешимость логики первого порядка 0(p) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y Неразрешимость логики первого порядка Неразрешимость логики первого порядка) → 0(s)A0y)


Мы требуем при этом, чтобы последовательность целых чисел p1,…, р,…, pv была возрастающей; р может совпадать с р1 или с рv Заметим, что формула (4) является описанием времени 0.

Предположим теперь, что машина, получив на входе число n, в конце концов останавливается. Тогда для некоторых s, i, p и j машина в момент s окажется в состоянии qi, считывая при этом клетку с номером р, содержащую символ aj, причем в программе машинной нет команды для комбинации qiaj.

Предположим, далее, что из множества формул Д следует некоторое описание G времени s. Поскольку I – модель для Д, формула G должно быть истинным в I. Поэтому G должно содержать в качестве конъюнктивных членов формулы 0(s)Qi0(p) и 0(s)Aj0(p) а потому из G должна следовать формула


$t $x (t Qi x Неразрешимость логики первого порядка t Ai x),


входящее одним из дизъюнктивных членов в H. Поэтому Н будет следовать из Д.

Остается лишь показать, что для всякого неотрицательного s, если только машина не останавливается до момента s, из Д следует некоторое описание времени s. Докажем это индукцией по s.

Основание индукции. Пусть s = 0. Множество Д содержит, а потому и влечет за собой предложение (4), являющееся описанием времени 0.

Шаг индукции. Предположим, что выделенное курсивом предложение верно (для s). Предположим, далее, что наша машина не остановилась до момента s + 1. Это значит, что она не остановилась ни до момента s, ни в самый момент s. Тогда из Д следует некоторое описание (8) времени s. Нужно доказать, что из Д следует и некоторое описание времени s+1.

Поскольку I – модель для Д, формула (8) истинна в I. Поэтому в момент s машина находится в состоянии qi, считывая при этом некоторую клетку (с номером р), в которой записан символ aj. Поскольку машина в момент s не остановилась, в ее программе должна присутствовать команда одного из видов


(a) qi aj → ak С qm

(б) qi aj → aj П qm

(в) qi aj → aj Л qm

Если имеется команда типа (а), то одна из формул множества Д есть


"x "y "t ((t Qi x Неразрешимость логики первого порядка t Aj x) → (t' Qk x Неразрешимость логики первого порядка t Ap x Неразрешимость логики первого порядка (y ≠ x → (t A0 y → t' A0 y Неразрешимость логики первого порядка … Неразрешимость логики первого порядка t An y → t' An y))))


Она вместе с (5), (6) и (8) влечет за собой формулу

0 (s+1) Qi0 (p) Неразрешимость логики первого порядка 0 (s+1) Aj10 (p1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0 (s+1) Aj0 (p) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0 (s+1) Ajv0 (pv) Неразрешимость логики первого порядка "y ((y ≠ 0 (p1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y ≠ 0 (p) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y ≠ 0 (pv)) → 0 (s+1) A0y),

являющуюся описанием времени s + 1.

Еcли имеется команда типа (б), то одна из формул множества Д есть


"x "y "t ((t Qi x Неразрешимость логики первого порядка t Aj x) → (t' Qk x' Неразрешимость логики первого порядка (t A0 y → t' A0 y) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка (t An y → t' An y)))


Из этого предложения, объединенного с (5), (6) и (8), следует, что для некоторого символа Неразрешимость логики первого порядка,


0(s+1)Qi0(p+1) Неразрешимость логики первого порядка 0(s+1)Неразрешимость логики первого порядка Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s+1)Aj0(p+1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s+1) Неразрешимость логики первого порядка Неразрешимость логики первого порядка "y ((y ≠ Неразрешимость логики первого порядка Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y ≠ 0(p+1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка y ≠ Неразрешимость логики первого порядка) → 0(s+1)A0y),


а это предложение является описанием времени s + 1.

Если имеется стрелка типа (в), то одна из формул множества Д есть


"x "y "t ((t Qi x' Неразрешимость логики первого порядка t Aj x') → (t' Qk x Неразрешимость логики первого порядка (t A0 y → t' A0 y) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка (t An y → t' An y)))


Тогда существует такой символ aq, что из последней формулы, объединенной с (5), (6), (8), следует

0(s+1)Qi0(p-1) Неразрешимость логики первого порядка 0(s+1)Неразрешимость логики первого порядка Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s+1)Aj 0(p-1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка 0(s+1)Неразрешимость логики первого порядка Неразрешимость логики первого порядка "y

((y Неразрешимость логики первого порядка Неразрешимость логики первого порядка y Неразрешимость логики первого порядка 0(p-1) Неразрешимость логики первого порядка … Неразрешимость логики первого порядка yНеразрешимость логики первого порядка) → 0(s+1)A0 y)


а это предложение является описанием времени s + 1.

Во всех трех случаях множество Д имеет следствием некоторое описание времени s + 1, и тем самым неразрешимость логики первого порядка доказана.

Доказательство неразрешимости логики первого порядка методом Геделя

Для доказательства неразрешимости логики первого порядка достаточно продемонстрировать, как по данной машине Т с входным значением n (то есть когда машина находится на самой левой единице в сплошной последовательности из n единиц при пустых символах в остальных клетках ленты) построить такие предложение I и конечное множество предложений Г, что машина Т при входном значении Неразрешимость логики первого порядка останавливается тогда и только тогда, когда Г ├ I.

Не существует эффективной процедуры, позволяющей решать, останавливается ли произвольная машина Тьюринга Т при произвольном входном значении 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.

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

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

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

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

если gi = Неразрешимость логики первого порядка, то "x1 … "xm … "xn gi(x1, …, xm, …, xn) = xm

Если gi получается из предшествующих ей функций gj и gk c помощью примитивной рекурсии, то "x gi(x, 0) =gj(x) и "x "y gi(x, y') =gk(x, y, gi(x, y))

Если же gi получается из предшествующих ей функций gо и Неразрешимость логики первого порядка путем композиции, то "x gi(x) =gjНеразрешимость логики первого порядка (для краткости заменили здесь x1, x2, …, xn на x, a "x1, "x2, …, "xn на "x)

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

Утверждение. Машина T при входном значении Неразрешимость логики первого порядка останавливается тогда и только тогда, когда Г ├ I.

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

«Только тогда». Предположим, что Т останавливается при входном значении Неразрешимость логики первого порядка. Для доказательства соотношения Г ├ I предположим, что Неразрешимость логики первого порядка – произвольная модель, в которой все предложения из Г истинны, и

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: