Calculul lambda: descrierea teoremei, caracteristici, exemple

Lambda-calculul este un sistem formal în logica matematică pentru exprimarea calculului bazat pe abstractizare și pe aplicarea funcțiilor folosind legarea și substituirea variabilelor. Este un model universal care poate fi aplicat la proiectarea oricărei mașini Turing. Lambda-calculul a fost introdus pentru prima dată de Church, un matematician celebru, în anii 1930.

Sistemul constă în construirea de membri lambda și efectuarea de operații de reducere asupra lor.

Explicații și aplicații

Litera grecească lambda (λ) este utilizată în expresiile lambda și în termenii lambda pentru a indica legarea unei variabile într-o funcție.

Lambda calculus poate fi netipată sau tipizată. În primul caz, funcțiile pot fi aplicate numai dacă sunt capabile să accepte date de acest tip. Typed lambda-calculus este mai slab, poate exprima o valoare mai mică. Dar, pe de altă parte, vă permit să dovediți mai multe lucruri.

Unul dintre motivele pentru care există mai multe tipuri diferite este dorința oamenilor de știință de a face mai mult fără a renunța la posibilitatea de a demonstra teoreme puternice ale calculului lambda.

Are aplicații în multe domenii diferite ale matematicii, filozofiei, lingvisticii și informaticii. În primul rând, calculul lambda este un calcul care a jucat un rol important în dezvoltarea teoriei limbajelor de programare. Este vorba de stilurile de creație funcțională care implementează sisteme. Ele reprezintă, de asemenea, o temă de cercetare actuală în teoria acestor categorii.

Pentru începători

Lambda-calculul a fost introdus de matematicianul Alonzo Church în anii 1930, ca parte a unui studiu al fundamentelor științei. Sistemul original s-a dovedit a fi inconsistent din punct de vedere logic în 1935, când Stephen Kline și J.J. Kline. Б. Rosser a dezvoltat paradoxul Kliney-Rosser.

Mai târziu, în 1936, Church a izolat și a publicat doar partea relevantă pentru calcul, ceea ce acum se numește lambda-calculul netipizat. În 1940 a prezentat și o teorie mai slabă, dar logic consistentă, cunoscută sub numele de sistemul de tip simplu. În lucrarea sa, el explică întreaga teorie în termeni simpli, astfel încât putem spune că Church a publicat calculul lambda pentru începători.

Până în anii 1960, când a devenit clară relația sa cu limbajele de programare, λ a fost doar un formalism. Datorită aplicațiilor lui Richard Montague și ale altor lingviști la semantica limbajului natural, calculul a câștigat un loc de onoare atât în lingvistică, cât și în informatică.

Originea simbolului

Lambda nu reprezintă un cuvânt sau o abreviere, ci își are originea într-o referință din Principiul matematicii lui Russell, urmată de două modificări tipografice. Exemplu de notație: pentru funcția f cu f (y) = 2y + 1 este 2ŷ + 1. Și în acest caz se folosește un simbol de cărămidă ("hat") peste y pentru a indica variabila de intrare.

Biserica a intenționat inițial să folosească simboluri similare, dar tipografii nu au putut plasa simbolul "pălăriei" deasupra literelor. Așa că în schimb au tipărit-o inițial ca /y.2y+1". În următorul episod de editare, tipografii au înlocuit "/ " cu un simbol vizual asemănător.

Introducere în calculul lambda

Sistemul constă dintr-un limbaj de termeni, care sunt aleși printr-o anumită sintaxă formală, și un set de reguli de transformare care permit manipularea lor. Ultimul punct poate fi văzut ca o teorie ecuațională sau ca o definiție operațională.

Toate funcțiile din lambda-calculus sunt anonime, adică fără nume. Acestea acceptă o singură variabilă de intrare, curricularea fiind folosită pentru a implementa grafuri cu mai multe non-variabile.

Termeni lambda

Sintaxa calculului definește unele expresii ca fiind permise și altele ca fiind invalide. La fel cum diferite șiruri de caractere sunt programe C valide, iar altele nu sunt. Expresia efectivă a calculului lambda se numește ""terminal lambda"".

Următoarele trei reguli oferă o definiție inductivă care poate fi aplicată pentru a construi toate conceptele valide din punct de vedere sintactic:

Variabila x în sine este un termen lambda valid:

• Dacă T este LT, iar x este neconstantă, atunci (lambda xt) se numește abstracție.
• dacă T, precum și conceptele s, atunci (TS) se numește o aplicație.

Nimic altceva nu este un termen lambda. Astfel, un concept este valid dacă și numai dacă poate fi obținut prin reaplicarea acestor trei reguli. Cu toate acestea, unele paranteze pot fi omise în funcție de alte criterii.

Definiție

Expresiile lambda constau în:

• variabilele v 1, v 2,..., v n,...
• simboluri de abstractizare ""λ"" și punct "".`
• paranteze ().

Setul Λ poate fi definit inductiv:

• Dacă x este o variabilă, atunci x ∈ Λ