Лямбда-исчисление без свободных переменных такое же сильное, как и лямбда-исчисление?

Question

Первый вопрос:Как можно было бы доказать, что, удаляя свободные (несвязанные) переменные из лямбда-исчисления и допуская только связанные переменные, его мощность не уменьшается (она по-прежнему является полной по Тьюрингу)?

Второй вопрос:Действительно ли приведенное выше утверждение верно?Действительно ли лямбда-исчисление без свободных переменных является полным по Тьюрингу?

Answer 1

Я предполагаю, что вы имеете в виду нетипизированное лямбда-исчисление.

Если да, напишите $ ewcommand{ um}[1]{\язвитель #1 \urcorner} um{n}$ для церковного счисления натурального числа $n$.

Известно, что существует замкнутый член (т.е. без свободных переменных). $ТМ$ такой , что $$ TM\ \число{i}\ \число{n}\ =_{\бета\эта} \ \число{m} $$ тогда, и только тогда, когда $я$-я машина Тьюринга (в некотором стандартном перечислении) запускается с вводом $n\в\mathbb N$ (кодируется как обычно) останавливает возврат $м$ в качестве выходных данных.

Действительно, написание $ТМ$ это стандартное упражнение по "программированию" в лямбда-исчислении.Для этого ленту можно представить в виде пары-или-пар-из-пар-of...(ОН ЖЕ список минусов) символов.Затем может быть записана "пошаговая" подпрограмма для продвижения ленты и состояния TM.Наконец, пошаговая подпрограмма вызывается до тех пор, пока не будет достигнуто состояние остановки.Этот последний шаг может быть достигнут с помощью комбинатора с фиксированной точкой, такого как $Y$.

Поскольку мы можем смоделировать любую машину Тьюринга, мы получаем полноту по Тьюрингу.

---

Альтернативное доказательство, которое (на мой взгляд) проще выполнить на самом деле во всех деталях:докажите, что любая общая рекурсивная функция может быть $\лямбда$-определяется с использованием замкнутого лямбда-термина.Для этого перейдем путем индукции к определению общей рекурсивной функции.

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

Поскольку общие рекурсивные функции - это именно те, которые могут быть вычислены машиной Тьюринга, мы получаем полноту по Тьюрингу для замкнутого лямбда-исчисления.