Teoria calculabilității
Teoria calculabilității , calculabilității și recursivității urmărește să înțeleagă ce funcții pot fi calculate printr-o procedură automată. Cu alte cuvinte, încearcă să determine dacă o funcție dată este teoretic calculabilă, indiferent dacă este, de asemenea , tratabilă , adică , indiferent de cantitatea de resurse pe care execuția sa o necesită în termeni de timp sau memorie, ceea ce la un nivel practic ar putea fi prohibitiv. Această disciplină este comună atât matematicii, cât și informaticii .
În consecință, obiectivul principal este de a oferi o definiție formală și riguroasă matematic a ideii intuitive a unei funcții calculabile . Pe de o parte, abordarea este de a aprofunda conceptul de calculabilitate, încercând să identifice categoriile de probleme teoretic rezolvabile și, pe de altă parte, să mapeze acest concept pe ceea ce este teoretic calculabil pe computere , întotdeauna fără a lua în considerare limitările impuse. după costuri, timp și cantitatea de memorie utilizată.
Un alt aspect important este definirea matematică a conceptului de algoritm, astfel încât programele să poată fi gândite concret în termeni de obiecte matematice, mai exact ca funcții care returnează un anumit rezultat pornind de la un anumit set de date de intrare.
Ce este un algoritm
O primă definiție a unui algoritm este următoarea: un algoritm este o secvență finită de instrucțiuni care definesc în mod clar și fără echivoc operațiile care trebuie efectuate pentru a obține un rezultat. De exemplu, raționamentul la un nivel ridicat de abstractizare,
- Înaintează 5 pași
- Vireaza la stanga
- Înaintează 7 pași
poate fi un algoritm pentru a ajunge la o anumită poziție. Cu toate acestea, această definiție nu epuizează pe deplin conceptul a ceea ce este un algoritm. Pentru a obține o definiție acceptabilă, au fost concepute mai multe moduri echivalente, de exemplu prin intermediul mașinilor Turing , funcțiilor parțiale recursive, sistemelor Post și Markov și mașinilor de înregistrare, rude apropiate ale computerelor moderne. S-a dovedit că toate aceste metode sunt echivalente una cu cealaltă, cu consecința că puterea de calcul, adică ceea ce pot calcula în principiu, este aceeași.
Deoarece atunci când scrieți un program în orice limbaj de programare, furnizați o secvență de instrucțiuni pentru a produce un anumit rezultat, putem spune că un algoritm este ceea ce ascunde o funcție care ia numerele naturale ca intrare și returnează numerele naturale. Dacă un algoritm calculează pe orice set A, este posibil să îi asociați o funcție parțială:
...
Funcții recursive parțiale
Funcțiile recursive parțiale sunt un exemplu de formalism capabil să definească conceptul unei funcții intuitive calculabile.
Se poate arăta că formalismul funcțiilor parțiale recursive are aceeași expresivitate ca și a mașinii Turing . Dovada se bazează pe implementarea unui interpret pentru o mașină Turing prin funcții parțiale recursive.
Teza Bisericii-Turing
Dacă o funcție este calculabilă conform oricărui formalism existent și inexistent, atunci este calculabilă și cu o mașină Turing .
Bibliografie
- Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi; Franco Angeli Editor: Limbi, modele, complexitate (2003) ( ISBN 88-464-4470-1 )
- Brainerd, WS, Landweber, LH (1974), Theory of Computation , Wiley, ISBN 0-471-09585-0
- Piergiorgio Odifreddi , The Classical Recursion Theory (1989 și 1999), două volume, Olanda de Nord.
