Классификация типизированных / нетипизированных лямбда-исчислений

18

Может кто-нибудь объяснить кратко (если это возможно!) Или отослать меня к ссылке, обобщающей различия между нетипизированным лямбда-исчислением и более распространенным типизированным лямбда-исчислением?

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

Хотя я, конечно, намереваюсь читать, что-то вроде справочной таблицы с изложением исчислений и их эквивалентностей / различий / места в иерархии было бы ОГРОМНЫМ справочником, чтобы помочь мне разобраться в них.

Не сказать, что ниже это правильно, просто пытаюсь набросать вместе некоторые из впечатлений, которые я должен увидеть, если они хотя бы служат отправной точкой (или что-то, чтобы исправить!)

Нетипизированное лямбда-исчисление - экв. к логике первого порядка - не могу сделать X

Проще говоря, лямбда-исчисление - eq to ... логика, связанная с Лиспом?

«Полиморфный» лямбда-кальций и т. Д.

Конструктивное исчисление - интуиционистская логика?

Комбинаторная логика - сравнима с ??? типизированное лямбда-исчисление, относящееся к языкам APL / J

Если это связано с лямбда-кубом и его тремя осями, тем лучше.

Несмотря на то, что я знаком с основами лямбда-исчисления и программирования с функциональными языками, я никогда не задумывался и не имел каких-либо существенных связей с системами типов и различными разновидностями лямбда-исчислений (и, возможно, пи?).

Когда я пытаюсь исследовать это, я не могу помочь, но оказываюсь в стороне, открывая множество вкладок браузера и разветвляясь в столь многих направлениях, что я никогда не вхожу ни в одну из них с какой-либо глубиной!

Я не уверен, разумно ли то, о чем я прошу, но, надеюсь, по крайней мере, я нарисовал достаточно картинок, чтобы предложить какое-то чтение, которое может объяснить, что я ищу?

jon_darkstar
источник
1
визуализация лямбда-куба, если возможно ссылка на него может помочь с объяснением rbjones.com/rbjpub/logic/cl/tlc001.htm
jon_darkstar
3
Личная история: когда я впервые изучал типизированное и нетипизированное лямбда-исчисление, меня всегда смущало, почему я должен заботиться о типизированных нетюринговых полных исчислениях. Это часто заставляло меня терять интерес. С другой стороны, меня это никогда не беспокоило, когда я думал о сложности и эффективных вычислениях. В конце концов, в этом ответе кто-то соединил для меня две составляющие, и теперь я могу лучше понять, почему так много времени было потрачено на обучение набранному лямбда-исчислению.
Артем Казнатчеев
я вижу lo.logicтег был добавлен. возможно глупый вопрос, но что именно это означает?
jon_darkstar
«Когда я пытаюсь исследовать это, я не могу помочь, но оказываюсь в стороне, открывая множество вкладок браузера и разветвляясь во многих направлениях, я никогда не получаю ни одного из них с какой-либо глубиной!» <- Это я все время! Спасибо, что спросили, о чем я думал ...
агам

Ответы:

26

Ваш стол немного запутан; вот лучше.

  • Как отмечает Андрей, нетипизированное лямбда-исчисление - без логической интерпретации
  • Простое типизированное лямбда-исчисление - интуиционистская логика высказываний
  • Полиморфное лямбда-исчисление - чистая логика второго порядка (т.е. без квантификаторов первого порядка)
  • Зависимые типы - обобщение логики первого порядка
  • Исчисление конструкций - обобщение логики высшего порядка

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

Вы также можете связать синтаксическую форму исчисления с логическими системами.

  • Комбинаторные исчисления (например, комбинаторы SKI). Гильбертовы системы
  • А-нормальная форма - исчисление секвенций
  • Обычное типизированное лямбда-исчисление - естественный вывод
Нил Кришнасвами
источник
фантастический! Благодарю. помогает мне понять мотивацию / различие для этих различных исчислений, и, безусловно, поможет мне сохранить базовое понимание, когда я прочитаю больше об этом
jon_darkstar
Я также включил бы типизированные лямбда-исчисления без логической интерпретации, такие как PCF. Кроме того, есть много интересных лямбда-исчислений, которые соответствуют другой логике, такой как линейное лямбда-исчисление.
Сэм Тобин-Хохштадт
@ Сэм: Хороший вопрос. «Никакая логическая интерпретация» на самом деле не является слишком сильной, поскольку она действительно означает «неограниченное использование собственных ссылок», что в сочетании с переменным повторным использованием приводит к несогласованности. Но некоторые теории множеств, основанные на линейной логике, поддерживают наивные схемы понимания без каких-либо противоречий.
Нил Кришнасвами
конечно, некоторые способы, которыми вы можете добавить некоторые вещи в лямбда-исчисление, не будучи противоречивыми. Но есть много интересных типизированных лямбда-исчислений без логической интерпретации в точном смысле нетипизированного лямбда-исчисления.
Сэм Тобин-Хохштадт
20

Чистый нетипизированный калькуляция является полным по Тьюрингу, т. Е. Частичное теоретико-числовое отображение вычислимо тогда и только тогда, когда оно определимо в нетипизированном λ- калькуляторе. Вычислительная мощность типизированного λ- исчисления намного меньше. Например, если мы добавим тип натуральных чисел к типизированному λ- вычислению вместе с 0 , преемником и примитивной рекурсией, мы получим то, что обычно известно как T Геделя . Он вычисляет только примитивно-рекурсивные функции (и все они суммарные).λλλnatλ0T

Нетипизированный калькуляция не имеет разумной интерпретации в соответствии с соответствием Карри-Говарда, в то время как типизированный λ- калькуляция точно соответствует интуиционистскому исчислению высказываний.λλ

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

λλλUlambda : U -> (U -> U)gamma : (U -> U) -> UλUλСUU[Соп,SеT]UUU

Ссылки:

Андрей Бауэр
источник