Фиксированные точки в вычислимости и логике

15

Этот вопрос также был размещен на Math.SE,

/math/1002540/fixed-points-in-computability-nd-logic

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


Я хотел бы лучше понять связь между теоремами о неподвижной точке в логике и -calculus.λ

Фон

1) Роль неподвижных точек в неполноте и неопределимости истины

Насколько я понимаю, помимо основной идеи интернализации логики, ключ к обеим доказательствам неопределимости Тарской истины и теорем о неполноте Гёделя является следующей теоремой логической фиксированной точки , живущей в конструктивной, finitistic метатеории (я надеюсь , что формулировка все в порядке, пожалуйста, исправьте меня, если что-то не так или неточно):

Наличие неподвижных точек в логике

Предположим, что - достаточно выразительная, рекурсивно перечислимая теория над языком , и пусть - кодировка -формул в , то есть алгоритм, преобразующий произвольные правильно сформированные -формулы в -формулы с одной свободной переменной , такой что для любого -формула у нас .L C L T L φ L C (φ)(v) L φ T! V: C (φ)(V)TLСLTLφLС(φ)(v)LφT!v:С(φ)(v)

Тогда существует алгоритм превращающий правильно сформированные -формулы из одной свободной переменной в замкнутые правильно сформированные -формулы, такой, что для любой -формулы в у нас есть одна свободная переменная который, интерпретируя как определенный символ функции , также может быть записан более компактно какL L L ф Т У (ф)v: С ( У (ф))(v)ф(v), С- Т У (ф)ф( У (ф)).YLLLφ

TY(φ)v:С(Y(φ))(v)φ(v),
С-
TY(φ)φ(Y(φ)),

Другими словами, является алгоритмом для построения неподвижных точек относительно -эквивалентности однопеременных -формул.T LYTL

Это имеет как минимум два приложения:

  • Применяя его к предикату выражающему « кодирует предложение, которое, когда создается его собственное кодирование, не доказуемо». дает формализацию «Это предложение не доказуемо», которое лежит в основе аргумента Геделя.vφ(v)v

  • Применение его к для произвольного предложения дает Тарски неопределимость истины.ϕ¬φφ

2) Фиксированные точки в нетипизированном -calculusλ

В нетипизированном исчислении построение неподвижных точек важно для реализации рекурсивных функций.λ

Существование неподвижных точек в -calculus:λ

Существует комбинатор с фиксированной точкой , т. Е. -терм такой, что для любой -терм мы имеемY λ f f ( Y f ) α β Y f .λYλе

е(Yе)~αβYе,

наблюдение

Что меня поразило, так это то, что комбинатор с фиксированной точкой в λ- калькуляторе очень чисто и нетехническим образом отражает обычное доказательство логической теоремы о неподвижной точке:λе,(λИкс,е(ИксИкс))(λИкс,е(ИксИкс))λ

Очень грубо , учитывая формулу , рассматривают формализацию φ ( v ) утверждения « v кодирует предложение, которое, когда создается его экземпляр, удовлетворяет ϕ », и ставит A ( ϕ ) : = φ ( φ ) . Предложение φ ( v ) похоже на λ x . f ( x x ) , а φ ( φ ) соответствуетφφ(v)vφA(φ)знак равноφ(φ)φ(v)λИкс,е(ИксИкс)φ(φ) .(λИкс,е(ИксИкс))(λИкс,е(ИксИкс))

Вопрос

Несмотря на быстро описанную идею, доказательство теоремы о фиксированной точке оказалось довольно техническим и трудным во всех деталях; Кунен делает это, например, в теореме 14.2 своей книги «Теория множеств». С другой стороны, комбинатор в λ- калькуляторе очень прост, и его свойства легко проверяются.Yλ

Строго ли вытекает теорема о неподвижной точке из логических комбинаторов с неподвижной точкой в вычислении?λ

Например, можно ли моделировать вычисление с помощью L- формул с точностью до логической эквивалентности, чтобы при интерпретации любого комбинатора с фиксированной точкой получался алгоритм, описанный в теореме о логической фиксированной точке?λL


редактировать

Ввиду множества других примеров того же аргумента диагонализации, описанного в ответах Мартина и Коди, следует перефразировать вопрос:

Существует ли общее обобщение аргументов диагонализации в соответствии с принципом, выраженным в комбинаторе? λ ф . ( λ x . f ( x x ) ) ( λ x . f ( x x ) )Y

λе,(λИкс,е(ИксИкс))(λИкс,е(ИксИкс))

Если я правильно понимаю, одно предложение - это теорема Лоувера о неподвижной точке , см. Ниже. К сожалению, однако, я не могу следовать соответствующим специализациям ни в одной из статей, которые Мартин цитировал в своем ответе, и я был бы рад, если бы кто-то мог их объяснить. Во-первых, для полноты:

Теорема Лавре о неподвижной точке

Пусть - категория с конечными произведениями и φ : A × A Y такая, что для любого морфизма f : A Y в C найдется некоторая f : 1 A такая, что для всех точек p : 1 A имеется 1 ре Y = 1 ре , идентификаторСφ:A×AYе:AYСе:1Aп:1A

1пA е Y  знак равно  1пAе,Я быAA×AφY,

Тогда для любого эндоморфизма , положив ф : = Д × ф Y г Y , любой выбор е приводит к фиксированной точке г , а именно : 1 е , е × ф Y .грамм:YY

е знак равно AΔA×AφYграммY,
еграмм
1е,еA×AφY,

Это утверждение в (интуиционистской) теории первого порядка категорий с конечными произведениями и, следовательно, применимо к любой модели последнего.

Например , если взять теоретическую вселенную в качестве области дискурса, весь парадокс Рассела (возьмем гипотетический набор множеств, Y : = Ω : = { 0 , 1 } и ρ : A × A Ω - -предикат) и теорема Кантора (возьмем A любое множество и ρ : A × A Ω, соответствующее гипотетическому предположению A Ω AAYзнак равноΩзнак равно{0,1}ρ:A×AΩAρ:A×AΩAΩA). Далее, перевод доказательства теоремы Лаврера дает обычные диагональные рассуждения.

Более конкретная проблема:

Может ли кто-нибудь подробно объяснить применение теоремы Лаврера к частичным рекурсивным функциям или теоремы о неподвижной точке? В частности, какие категории нам нужно рассмотреть там?

В D. Pavlovic, О структуре парадоксов , автор считает категорию, свободно порожденную с End ( N ) частичными рекурсивными функциями.NКонец(N)

К сожалению, я не понимаю, что это значит.

Конец(N)Aзнак равноYзнак равноNNN1N1NN1N тоже только частичная функция, следовательно, может быть неопределенной, теорема о неподвижной точке тривиальна.

Какую категорию вы действительно хотите рассмотреть?

Возможно, цель состоит в том, чтобы получить теорему Роджера о неподвижной точке, но тогда нужно как-то встроить кодирование частично рекурсивных функций натуральными числами в определение категории, и я не могу понять, как это сделать.

Я был бы очень рад, если бы кто-то мог объяснить конструкцию контекста, к которому применяется теорема Лаврэра о неподвижной точке, давая начало теореме о логической неподвижной точке или теореме о неподвижной точке для частично рекурсивных функций.

Спасибо!

Ханно Беккер
источник
1
Qλ
@ EmilJeřábek: Спасибо за ваш комментарий! Я понимаю, что не будет никакого способа обойти кодирование рекурсивных функций, но я хотел бы четко отделить, что касается кодирования и что будет формальным впоследствии.
Ханно Беккер,
λY
φN(NN)(NN)(NN)Y
Коди, не мог бы ты уточнить, какую именно категорию ты используешь, потому что я не могу следить за другими источниками.
Ханно Беккер

Ответы:

7

Я, вероятно, не отвечаю прямо на ваш вопрос, но есть общее математическое обобщение многих парадоксов, включая теоремы Геделя и Y-комбинатор. Я думаю, что это было впервые исследовано Lawvere. Смотрите также [2, 3].

  1. Ф. В. Лавре, Диагональные аргументы и декартовы замкнутые категории .

  2. Д. Павлович, О структуре парадоксов .

  3. Янофский Н.С. Универсальный подход к самореференциальным парадоксам, неполноте и неподвижным точкам .

Мартин Бергер
источник
Lind1×Lind1Lind0
@HannoBecker Это может быть довольно сложно и чувствительно к кодированию.
Мартин Бергер
5

У меня нет полного ответа на ваш вопрос, но у меня есть это:

Согласно Википедии говорит

Q(x,y)p

φпλY,Q(п,Y)
φN

λ

φTN

Tφ(N¯)TY,φN(Y)знак равно0

Это не совсем то, что вы хотите, но уловка интернализации может дать вам более сильное утверждение

Tφ(N¯)Y,φN(Y)знак равно0

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

Q(Икс,Y)

Q(Икс,Y)знак равно0 тогда и только тогда Tφ(Икс¯) самое большее Y меры
QY,Q(Икс,Y)Tφ(Икс¯)TY,Q(Икс¯,Y)ωQ

Немного подумав, вы, вероятно, сможете усилить этот аргумент, чтобы получить полную теорему напрямую без интернализации.

Коди
источник
φ:NС(N,N)
С(N2,N)карта(N,С(N,N))карта(N,N)
С(N,N)N2N(N,м)φ(N)(м)
Yλ
φYY ее(Y е)пзнак равноY QλquoteevalY