C??lcul lambda
De Viquip??dia
El c??lcul lambda ??s un sistema formal dissenyat per investigar la definici?? de funci??, la noci?? d'aplicacions de funcions i la recursi??. Fou introdu??t per Alonzo Church i Stephen Kleene a la d??cada de 1930; Church va usar el c??lcul lambda al 1936 per resoldre el Entscheidungsproblem. Pot ser usat per definir de manera neta i precisa qu?? ??s una ???funci?? computable???.
Church va resoldre negativament el Entscheidungsproblem: va provar que no hi ha algorisme que pugui ser considerat com una "soluci??" al Entscheidungsproblem.
El c??lcul lambda ha influ??t enormement en el disseny de llenguatges de programaci?? funcionals, especialment LISP.
Es pot considerar al c??lcul lambda com el m??s petit llenguatge universal de programaci??. Consisteix en una regla de transformaci?? simple (substituci?? de variables) i un esquema simple per definir funcions.
El c??lcul lambda ??s universal perqu?? qualsevol funci?? computable pot ser expressada i avaluada mitjan??ant ell. Per tant, ??s equivalent a les m??quines de Turing. Tot i aix??, el c??lcul lambda no fa ??mfasi en l'??s de regles de transformaci?? i no considera les m??quines reals que puguin implementar-lo. Es tracta doncs d'una proposta m??s propera al programari que al maquinari.
