Предварительные условия для обучения исчислению лямбда

Question

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

Answer 1

Это действительно зависит от того, что вы хотите делать с исчислением Lambda. Если вы хотите узнать это, просто чтобы увидеть, как это работает, на самом деле не предварительно невозможности; Это довольно автономно. Однако, если вы хотите понять какое-либо из доказательств об этом (Turing-Comploreness, церковные цифры, нормализация и т. Д.), Вам может потребоваться больше математических предварительных условий. В частности, я бы предложил фон в методах индуктивного доказательства, особенно структурной индукции. Также было бы неплохо узнать немного о проблеме остановки, либо о какой-то теореме неполноты, поскольку некоторые из забавных результатов с исчислением лямбда связаны с некомпьютеемости.

Answer 2

Нет никаких предпосылок для понимания самого исчисления Lambda. Если вы не являетесь компьютерным ученым и даже не знаете рекурсию, вы можете выяснить основы (нетипированного) исчисления лямбды примерно через 30 минут здесь: http://palmstroeem.blogspot.de/2012/05/lambda-calculus-for-absolute-dummies.html Это должно дать вам рабочую интуицию о том, что он делает и как это работает.

Если вы знакомы с основными математическими обозначениями и рекурсивными определениями, вы можете выбрать стандартное введение. Особенно, если вы хотите узнать о исчислении Lambda в качестве основы для Haskell, вы должны углубиться в глубины исчисленного исчисления Lambda: http://www.cse.chalmers.se/research/group/logic/typesss05/extra/geuvers.pdf