Вопросы с тегом «lambda-calculus»

12
Эта разложение в паттерне лямбда-исчисления

У Клопа, ван Оострома и де Врийера есть статья о лямбда-исчислении с узорами. http://www.sciencedirect.com/science/article/pii/S0304397508000571 В некотором смысле шаблон - это дерево переменных - хотя я просто думаю о нем как о вложенном кортеже переменных, например, ((x, y), z), (t, s)). В статье...

12
Доказательство Барендрегтом предметной редукции для

Я нашел проблему в доказательстве понижения субъекта Барендрегтом (Thm 4.2.5. Лямбда-исчисления с типами ). Последний шаг доказательства (стр. 60) гласит: "и, следовательно, по лемме 4.1.19 (1), Γ,x:ρ⊢P:σ′Γ,x:ρ⊢P:σ′\quad\Gamma,x:\rho\vdash P:\sigma' . " Однако согласно лемме 4.1.19 (1) это должно...

12
Функции, которые напечатали лямбда-исчисление, не могут вычислить

Я просто хочу знать некоторые примеры функций, которые могут быть вычислены нетипизированным лямбда-исчислением, но не типизированными лямбда-исчислениями. Поскольку я новичок, некоторые повторение справочной информации будет оценено. Благодарю. Редактировать: набрав лямбда-исчисление, я...

11
Простое типизированное лямбда-исчисление и логика высшего порядка

Какова связь между просто типизированным лямбда-исчислением и логикой более высокого порядка? При Карри-Говарде кажется, что просто типизированное лямбда-исчисление соответствует логике высказываний. Как это связано с логикой высшего порядка? Согласно этому руководству Geuvers:...

11
Имеет ли система F с парами сильные свойства нормализации и сокращения объекта?

Во многих учебниках легко найти доказательства сокращения предмета и строгой нормализации для Системы F, а также иногда есть определения Системы F с парами, где (t, r) - это термин, а не только кодировка. Вопрос в том, что будет ссылкой на эту...

11
Эквивалентная формулировка теории сложности в лямбда-исчислении?

В теории сложности определение сложности времени и пространства ссылается на универсальную машину Тьюринга: соотв. количество шагов до остановки и количество ячеек на ленте, которых коснулись. Учитывая тезис Черча-Тьюринга, должно быть возможно определить сложность и в терминах лямбда-исчисления....

11
Какой смысл называть

Какая разница в том, чтобы называть калькуляцию алгеброй вместо исчисления? Я поднимаю этот вопрос, потому что где-то прочел строку « λ- калькуляция - это не исчисление, а алгебра» (iirc, приписывается Дане Скотт). Какой смысл?...

11
Расширение моделей лямбда-исчисления

Я перевожу книгу на LISP и, естественно, она затрагивает некоторые элементы калькуляции. Таким образом, понятие экстенсиональности упоминается там наряду с некоторыми моделями λ- вычисления, а именно: P ω и D ∞ (да, с бесконечностью вверху). И говорят, что P ω экстенсиональна, а D ∞...

11
Представление связанных переменных с помощью функции от использования к связующим

Проблема представления связанных переменных в синтаксисе и, в частности, проблема подстановки во избежание захвата, хорошо известна и имеет ряд решений: именованные переменные с альфа-эквивалентностью, индексы де Брейна, локальное безымянность, именные множества и т. Д. Но, похоже, есть еще один...

11
Почему лямбда-исчисление является «исчислением»?

Единственное определение «исчисления», которое я знаю, - это изучение пределов, производных, интегралов и т. Д. В анализе. В каком смысле лямбда-исчисление (или такие вещи, как mu calculus) является «исчислением»? Как это связано с исчислением в...

11
Исчисление конструкций: сжать выражение до его наименьшей формы

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

11
Наследственное замещение с иерархией вселенной

Я читал о наследственной замене Простого лямбда-исчисления и Логической структуры с различными терминами и типами. Мне интересно, есть ли примеры наследственного замещения в зависимо типизированной системе с иерархией юниверсов? то есть где и т. д.True:Set0:Set1:Set2True:Set0:Set1:Set2 True : Set_0...

10
Как вы кодируете абстрактный алгоритм Лампинга, используя комбинаторы взаимодействия?

Комбинаторы взаимодействия были предложены в качестве цели компиляции для λ-исчисления ранее. Эта статья реализует полное λ-исчисление. Известно также, что можно оптимизировать кодировки сети взаимодействия λ-исчисления для подмножества λ-членов, которое можно типом EAL. Эта статья реализует это...

10
Можно ли сортировать `sort` по элементарной аффинной логике?

Следующий λ-член здесь в нормальной форме: sort = (λabc.(a(λdefg.(f(d(λhij.(j(λkl.(k(λmn.(mhi))l)) (h(λkl.l)i)))(λhi.(i(λjk.(bd(jhk)))(bd(h(λjk.(j (λlm.m)k))c)))))e))(λde.e)(λde.(d(λfg.g)e))c)) Реализует алгоритм сортировки для церковно-закодированных списков. То есть результат: sort (λ c n . (c 3...

10
В чем разница между стратегиями сокращения и оценочными стратегиями?

Из статьи по стратегии оценки в Википедии: Понятие стратегии сокращения в лямбда-исчислении сходно, но различно. Из статьи о стратегии сокращения в Википедии: Это похоже на понятие стратегии оценки в информатике, но немного отличается от него. Какое тонкое различие между стратегиями оценки и...

10
Оптимальные оценщики на самом деле оптимальны?

Следующий термин (используя bruijn-индексы): BADTERM = λ((0 λλλλ((((3 λλ(((0 3) 4) (1 λλ0))) λλ(((0 4) 3) (1 0))) λ1) λλ1)) λλλ(2 (2 (2 (2 (2 (2 (2 (2 0))))))))) Применительно к церковному номеру Nбыстро оценивается нормальная форма в нескольких существующих оценщиках, включая наивных . Тем не...

10
Алгоритмы инверсии программ для программ высшего порядка

Термин « инверсия программы» имеет несколько оттенков смысла, но, вероятно, он начался с работы Дж. Маккарти 1956 года «Обращение функций, определенных машинами Тьюринга в контексте ИИ». К настоящему времени обнаружено множество связей между инверсией программы и другими областями, например,...

10
Неполная основа комбинаторов

Это вдохновлено этим вопросом. Пусть будет совокупностью всех комбинаторов, которые имеют только две связанные переменные. Является ли C комбинаторно полным?СC\mathcal{C}СC\mathcal{C} Я считаю, что ответ отрицательный, однако я не смог найти ссылку для этого. Я также был бы заинтересован в ссылках...

10
Доказательные методы, чтобы показать, что проверка зависимого типа является разрешимой

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

10
Ссылка для неопределимости модуля непрерывности функционала в ПКФ?

Может ли кто-нибудь указать мне на ссылку на неопределяемость модуля функционала непрерывности в PCF? \newcommand{\N}{\mathbb{N}} \newcommand{\bool}{\mathsf{bool}} Андрей Бауэр написал очень хороший пост в блоге, в котором более подробно рассматриваются некоторые вопросы, но я кратко изложу его...