Теория алгоритмов. Зюзысов В.М. - 44 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Для n, m∈N положим h(n, m) = код результата подстановки терма <m> вместо
единственной свободной переменной в формулу с кодом n.
Функция h является вычислимой. Действительно, зная n, можно проверить,
является ли n формулой. Если это так, то алгоритмическим способом можно отыскать
свободную переменную в формуле и убедиться, что
она единственная. По номеру m
определяем соответствующий терм. Подстановка терма <m> вместо свободной
переменной в формулу описывается алгоритмом, как и последующее вычисление
геделевского номера. По тезису Черча, функция h – частично рекурсивна. Она не
определена в тех случаях, когда n не является номером формулы, или формула не
обладает единственной свободной переменной, или m
не является номером терма.
Когда значение функции определено, то имеем равенство
h( #F(x), m) = #F(<m>). (2)
Поскольку h – частично рекурсивная функция, то она представима в EA, т. е.
существует формула H(x
1
, x
2
, x
3
) в EA со свободными переменными x
1
, x
2
, x
3
, такая, что
|– H(<n>, <m>, <h(n, m)>),
|– ∀y(¬(y = <h(n, m)>) ⊃ ¬ H(<n>, <m>, y)).
Для любых термов x
1
, x
2
если и существует, то единственный терм y, обладающим
свойством H(x
1
, x
2
, y). Поэтому мы можем ввести в EA (не усиливая первоначальную
теорию) новый двухместный функциональный символ sub, такой, что
|– sub(<n>, <m>) = <h(n, m)>. (3)
Положим теперь натуральные v = #A(sub(x, x))) и n = h(v, v). Тогда
n = h(v, v) = h(#A(sub(x, x)), v) = #A
(sub(<v>, <v>) (в силу (2)) ~ #A(<h(v,v)>) = #A(<n>).
Отношение ~ между числами имеет место потому, что в силу (3) из свойства равенства
следует, что
|– A(sub(<n>, <m>)) ~ A(<h(n, m)>).
Теорема Гёделя о неполноте
Когда вопрос простой – ответ таким же будет.
Когда ж вопрос скрипит в зубах
Песком, попавшим в кашу,
Ответ – как прут, торчащий из земли.
Дверь без двери (Мумонкан)
Итак, лемма об рефлексии позволяет воспроизвести различные утверждения о
свойствах формул. Можно ли воспроизвести парадокс лжеца средствами EA? Какие это
будет иметь последствия?
Формула
–аналог утверждения «Я лгу» должна утверждать: «Меня можно
опровергнуть в EA» (вместо истинности и ложности в EA фигурируют доказуемость и
опровержимость). Если
F: «¬F доказуема в EA»,
то
¬F: «¬F недоказуема в EA»,
поэтому с тем же успехом мы можем рассматривать формулу
F: «F недоказуема в EA»,
она также
«равносильна» парадоксу лжеца. Именно такой формулой занимался в свое
время К. Гёдель, и мы не будем нарушать традицию.

Страницы