Теорема Трахтенброца - Trakhtenbrots theorem - Wikipedia

В логика, теория конечных моделей, и теория вычислимости, Теорема Трахтенброта (из-за Борис Трахтенброт ) утверждает, что проблема срок действия в логика первого порядка на классе всех конечных моделей есть неразрешимый. Фактически, класс действительных предложений над конечными моделями не является рекурсивно перечислимый (хотя это ко-рекурсивно перечислимый ).

Из теоремы Трахтенброта следует, что Теорема Гёделя о полноте (что является фундаментальным для логики первого порядка) не выполняется в конечном случае. Также кажется нелогичным, что быть валидным для всех структур «легче», чем только для конечных.

Теорема была впервые опубликована в 1950 году: «Невозможность алгоритма для проблемы разрешимости на конечных классах».^[1]

Математическая формулировка

Мы следуем формулировкам как в ^[2]

Теорема

Конечный выполнимость не разрешимо в логика первого порядка.

То есть множество {φ | φ - предложение логики первого порядка, выполнимое в конечном}, неразрешимо.

Следствие

Пусть σ - реляционный словарь с хотя бы одним символом двоичного отношения.

Набор σ-предложения действительно во всех конечных структурах не рекурсивно перечислимый.

Замечания

1. Отсюда следует, что Теорема Гёделя о полноте не работает в конечном, поскольку полнота предполагает рекурсивную перечислимость.
2. Отсюда следует, что не существует рекурсивной функции f такой, что: если φ имеет конечную модель, то она имеет модель размера не более f (φ). Другими словами, нет эффективного аналога Теорема Левенгейма – Сколема в конечном.

Интуитивное доказательство

Это доказательство взято из раздела 4, 5 главы 10 «Математической логики» Х.-Д. Эббингауз.

Как и в наиболее распространенном доказательстве Первая теорема Гёделя о неполноте за счет использования неразрешимости проблема остановки, для каждого Машина Тьюринга ${\displaystyle M}$ есть соответствующее арифметическое предложение ${\displaystyle \phi _{M}}$, эффективно выводимая из ${\displaystyle M}$, что истинно тогда и только тогда, когда ${\displaystyle M}$ останавливается на пустой ленте. Интуитивно ${\displaystyle \phi _{M}}$ утверждает, что "существует натуральное число, которое является кодом Гёделя для записи вычисления ${\displaystyle M}$ на пустой ленте, которая заканчивается остановкой ».

Если машина ${\displaystyle M}$ останавливается за конечные шаги, тогда полная запись вычислений также конечна, тогда существует конечный начальный отрезок натуральных чисел такой, что арифметическое предложение ${\displaystyle \phi _{M}}$ верно и на этом начальном участке. Интуитивно это происходит потому, что в данном случае доказательство ${\displaystyle \phi _{M}}$ требует арифметических свойств только конечного числа чисел.

Если машина ${\displaystyle M}$ не останавливается конечными шагами, то ${\displaystyle \phi _{M}}$ ложно в любой конечной модели, поскольку нет конечной записи вычислений ${\displaystyle M}$ это заканчивается остановкой.

Таким образом, если ${\displaystyle M}$ остановки, ${\displaystyle \phi _{M}}$ верно в некоторых конечных моделях. Если ${\displaystyle M}$ не останавливается, ${\displaystyle \phi _{M}}$ ложно во всех конечных моделях. Так, ${\displaystyle M}$ не останавливается тогда и только тогда, когда ${\displaystyle \neg \phi _{M}}$ верно для всех конечных моделей.

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

Альтернативное доказательство

В этом разделе мы показываем более строгое доказательство Либкина.^[3] Обратите внимание, что в приведенном выше утверждении следствие также влечет за собой теорему, и это направление мы и докажем здесь.

Теорема

Для каждого реляционного словаря τ с хотя бы одним символом бинарного отношения неразрешимо, является ли предложение φ словаря τ конечно выполнимым.

Доказательство

Согласно предыдущей лемме, на самом деле мы можем использовать конечное число символов двоичных отношений. Идея доказательства аналогична доказательству теоремы Феджина, и мы кодируем машины Тьюринга в логике первого порядка. Мы хотим доказать, что для каждой машины Тьюринга M мы построим предложение φ_M словаря τ такой, что φ_M конечно выполнимо тогда и только тогда, когда M останавливается на пустом входе, что эквивалентно проблеме остановки и, следовательно, неразрешимо.

Пусть M = ⟨Q, Σ, δ, q₀, Q_а, Q_р⟩ Быть детерминированной машиной Тьюринга с одной бесконечной лентой.

• Q - множество состояний,
• Σ - входной алфавит,
• Δ - ленточный алфавит,
• δ - переходная функция,
• q₀ начальное состояние,
• Q_а и Q_р представляют собой наборы принимающих и отклоняющих состояний.

Поскольку мы имеем дело с проблемой остановки на пустом входе, мы можем предположить, что w.l.o.g. что Δ = {0,1} и что 0 представляет собой пробел, а 1 представляет собой некоторый символ ленты. Мы определяем τ так, чтобы мы могли представить вычисления:

τ: = {<, мин, Т₀ (⋅, ⋅), T₁ (⋅, ⋅), (H_q(⋅,⋅))_{(q ∈ Q)}}

Где:

• <- линейный порядок и мин является постоянным символом для минимального элемента относительно <(наша конечная область будет связана с начальным отрезком натуральных чисел).
• Т₀ и т₁ предикаты ленты. Т_я(s, t) указывает, что позиция s в момент времени t содержит i, где i ∈ {0,1}.
• ЧАС_q- это главные предикаты. ЧАС_q(s, t) указывает, что в момент времени t машина находится в состоянии q, а ее головка находится в положении s.

Предложение φ_M утверждает, что (i) <, мин, Т_я's и H_qинтерпретируются, как указано выше, и (ii) машина в конечном итоге останавливается. Условие остановки эквивалентно тому, что H_{q ∗}(s, t) выполняется для некоторых s, t и q ∗ ∈ Q_а ∪ Q_р и после этого состояния конфигурация машины не меняется. Конфигурации останавливающейся машины (негальтинг не конечен) могут быть представлены как τ (конечное) предложение (точнее, конечная τ-структура, которая удовлетворяет этому предложению). Предложение φ_M есть: φ ≡ α ∧ β ∧ γ ∧ η ∧ ζ θ.

Разберем по составляющим:

• α утверждает, что <- линейный порядок и что мин его минимальный элемент
• γ определяет начальную конфигурацию M: он находится в состоянии q₀, голова находится в первой позиции и на ленте одни нули: γ ≡ H_q0(мин,мин) ∧ ∀s T₀ (s, мин)
• η утверждает, что в любой конфигурации M каждая ячейка ленты содержит ровно один элемент из ∆: ∀s∀t (T₀(s, t) → ¬ T₁(s, t))
• β накладывает основное условие согласованности на предикаты H_q's: в любой момент машина находится точно в одном состоянии:

${\displaystyle \forall t\exists !s(\bigvee _{q\in Q}H_{q}(s,t))\land \neg \exists s\exists t(\bigvee _{q,q'\in Q,q\neq q}H_{q}(s,t)\land H_{q'}(s,t))}$

• ζ утверждает, что в какой-то момент M находится в состоянии остановки:

${\displaystyle \exists s\exists t\bigvee _{q\in Q_{a}\cup Q_{r}}H_{q}(s,t)}$

• θ состоит из конъюнкции предложений, утверждающих, что T_я's и H_q's хорошо ведут себя по отношению к переходам M. В качестве примера, пусть δ (q, 0) = (q', 1, left) означает, что если M находится в состоянии q, читая 0, то он записывает 1, перемещает голова на одну позицию влево и переходит в состояние q '. Представим это условие дизъюнкцией θ₀ и θ₁:

${\displaystyle \theta _{0}\equiv \forall s\forall t(s\neq {\underline {min}}\land T_{0}(s,t)\land H_{q}(s,t))\to \theta _{2}}$

Где θ₂ является:

${\displaystyle T_{1}(s,t+1)\land H_{q'}(s-1,t+1)\land \forall s'(s\neq s'\to (\bigwedge _{i=0,1}T_{i}(s',t+1)\leftrightarrow T_{i}(s',t)))}$

И:

${\displaystyle \theta _{1}\equiv \forall s\forall t(s={\underline {min}}\land T_{0}(s,t)\land H_{q}(s,t))\to \theta _{3}}$

Где θ₃ является:

${\displaystyle T_{1}(s,t+1)\land H_{q'}(s,t+1)\land \forall s'(s\neq s'\to (\bigwedge _{i=0,1}T_{i}(s',t+1)\leftrightarrow T_{i}(s',t)))}$

s-1 и t + 1 - это определяемые сокращения первого порядка для предшественника и преемника в соответствии с порядком <. Предложение θ₀ гарантирует, что содержимое ленты в позиции s изменяется с 0 на 1, состояние изменяется с q на q ', остальная часть ленты остается той же, и что головка перемещается в s-1 (т.е. на одну позицию влево), предполагая s - не первая позиция в ленте. Если это так, то все обрабатывается θ₁: все то же самое, только голова не движется влево, а остается на месте.

Если φ_M имеет конечную модель, а затем такую ​​модель, которая представляет вычисление M (которое начинается с пустой ленты (т. е. ленты, содержащей все нули) и заканчивается в состоянии остановки). Если M останавливается на пустом входе, то множество всех конфигураций остановки вычислений M (закодированных с помощью <, T_я's и H_qs) является моделью φ_M, что конечно, так как конечно множество всех конфигураций остановки вычислений. Отсюда следует, что M останавливается на пустом входе тогда и только тогда, когда φ_M имеет конечную модель. Поскольку остановка на пустом входе неразрешима, остается вопрос, действительно ли φ_M имеет конечную модель ${\displaystyle {\mathcal {A}}}$ (эквивалентно, будет ли φ_M конечно выполнимо) также неразрешимо (рекурсивно перечислимо, но не рекурсивно). Это завершает доказательство.

Следствие

Множество конечно выполнимых предложений рекурсивно перечислимо.

Доказательство

Пронумеровать все пары ${\displaystyle ({\mathcal {A}},\phi )}$ куда ${\displaystyle {\mathcal {A}}}$ конечно и ${\displaystyle {\mathcal {A}}\models \phi }$.

Следствие

Для любого словаря, содержащего хотя бы один символ двоичного отношения, множество всех конечно действительных предложений не является рекурсивно перечислимым.

Доказательство

Из предыдущей леммы множество конечно выполнимых предложений рекурсивно перечислимо. Предположим, что множество всех конечно верных предложений рекурсивно перечислимо. Поскольку ¬φ конечно верно тогда и только тогда, когда φ не является конечно выполнимым, мы заключаем, что множество предложений, которые не являются конечно выполнимыми, рекурсивно перечислимо. Если и множество A, и его дополнение рекурсивно перечислимы, то A рекурсивно. Отсюда следует, что множество конечно выполнимых предложений рекурсивно, что противоречит теореме Трахтенброта.

Рекомендации

1. Трахтенброт Борис (1950). «Невозможность алгоритма проблемы разрешимости на конечных классах». Известия АН СССР. (на русском). 70 (4): 569–572.
2. Эббингаус, Хайнц-Дитер; Флум, Йорг (1995). Теория конечных моделей. Springer Science + Business Media. ISBN  978-3-540-60149-4.
3. Либкин Леонид (2010). Элементы теории конечных моделей. Тексты по теоретической информатике. ISBN  978-3-642-05948-3.

• Булос, Берджесс, Джеффри. Вычислимость и логика, Издательство Кембриджского университета, 2002.
• Симпсон, С. "Теоремы Чёрча и Трахтенброта". 2001 г.[1]