Prerequisiti per l'apprendimento lambda calcolo

Question

Qualcuno può dirmi quali sono i prerequisiti per l'apprendimento lambda calcolo (se del caso)?

Answer 1

Dipende da cosa si vuole fare con il lambda calcolo. Se volete imparare solo per vedere come funziona in realtà non sono dei prerequisiti; è abbastanza autosufficiente. Tuttavia, se si vuole comprendere alcuna delle prove su di esso (Turing-completezza, numeri Chiesa, la normalizzazione, ecc) potrebbe essere necessario più prereqs matematica. In particolare, io suggerirei un background in tecniche di dimostrazione induttiva, in particolare l'induzione strutturale. Potrebbe anche essere bello conoscere un po 'sia il problema della terminazione o una sorta di teorema di incompletezza, dal momento che alcuni dei risultati di divertimento con lambda calcolo implicano non computabilità.

Answer 2

Non ci sono prerequisiti per la comprensione del lambda calcolo stesso. Se non sei un informatico e non si sa nemmeno ricorsione, è possibile imparare le basi del (non tipizzato) Lambda Calcolo informalmente in circa 30 minuti qui: http://palmstroem.blogspot.de/2012/05/lambda-calculus-for-absolute-dummies.html Questo dovrebbe dare un'intuizione di lavoro su quello che fa e come funziona.

Se si ha familiarità con notazioni matematiche di base e definizioni ricorsive, si può andare per un'introduzione standard. Soprattutto, se si vuole conoscere la Lambda Calcolo come base per Haskell, si dovrebbe scavare nelle profondità del digitato lambda calcolo: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf