Предпосылки для изучения лямбда-исчисления
Может кто-нибудь сказать мне, каковы предпосылки для изучения лямбда-исчисления (если таковые имеются)?
2 ответа
Это действительно зависит от того, что вы хотите сделать с лямбда-исчислением. Если вы хотите изучить его, просто чтобы посмотреть, как он работает, на самом деле нет никаких предварительных условий; это довольно автономно. Однако, если вы хотите понять какие-либо доказательства об этом (полнота по Тьюрингу, церковные цифры, нормализация и т. Д.), Вам может понадобиться больше математических заданий. В частности, я бы предложил опыт работы с методами индуктивного доказательства, особенно со структурной индукцией. Также было бы неплохо немного узнать либо о проблеме остановки, либо о некоторой теореме о неполноте, поскольку некоторые из забавных результатов с лямбда-исчислением включают невычислимость.
Нет никаких предпосылок для понимания самого Лямбда-исчисления. Если вы не специалист по информатике и даже не знаете рекурсию, вы можете неформально освоить основы (нетипизированного) лямбда-исчисления примерно за 30 минут здесь: http://palmstroem.blogspot.de/2012/05/lambda-calculus-for-absolute-dummies.html Это должно дать вам рабочую интуицию о том, что он делает и как он работает.
Если вы знакомы с основными математическими обозначениями и рекурсивными определениями, вы можете перейти к стандартному введению. Особенно, если вы хотите узнать о лямбда-исчислении как основе для Haskell, вам следует углубиться в глубины типизированного лямбда-исчисления: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf