Парадокс Клини — Россера

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску


Парадокс Клини — Россера — математический парадокс, показывающий, что определённые системы формальной логики являются противоречивыми. В частности, это затрагивает версию комбинаторной логики, предложенную Хаскеллом Карри в 1930 году, а также исходный вариант лямбда-исчисления, разработанный Алонзо Чёрчем в 1932—1933. Парадокс был представлен Стивеном Клини и Джоном Россером[en] в 1935 году.

Парадокс[править | править код]

Клини и Россер продемонстрировали, что обе указанные системы позволяют охарактеризовать и перечислить всю общность доказуемо полных (то есть, всюду определённых) теоретико-числовых функций, что, в свою очередь, позволило им сконструировать объект, схожий по своим свойствам с числом Ришара. Из существования такого объекта, в свою очередь, следовала противоречивость указанных формальных систем.

Позднее Хаскелл Карри развил идеи, заложенные в парадоксе Клини — Россера, что привело к появлению гораздо более простого парадокса Карри.

Литература[править | править код]