Calculabilitate

Teoria calculabilității eficiente tratează existența sau nu a algoritmilor de rezolvare a problemelor. Printre fondatorii săi se numără Alan Turing .

Caracteristici ale existenței

Se spune că o funcție este calculabilă dacă există un algoritm care o calculează. În termeni matematici, se spune că un algoritm calculează o funcție $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ dacă, pentru fiecare valoare posibilă $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ a variabilei independente, atribuind această valoare ca intrare a algoritmului, algoritmul dă ca rezultat $f(x_{0})$ ${\ displaystyle f (x_ {0})}$ $f (x_0)$ .

Exemplu de funcție

Exemplu. Functia $f(x)=2x$ ${\ displaystyle f (x) = 2x}$ ${\ displaystyle f (x) = 2x}$ , pentru $x\in \mathbb {N}$ ${\ displaystyle x \ in \ mathbb {N}}$ $x \ in {\ mathbb N}$ , este calculabil. De fapt, se știe că diferiți algoritmi găsesc de două ori un număr natural. Exemplul anterior se referă la ansamblu $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb N$ a numerelor naturale, mai degrabă decât a întregului $\mathbb {R}$ ${\ displaystyle \ mathbb {R}}$ $\ mathbb R$ din regale. Acest lucru se datorează faptului că numerele reale, cu unele excepții, nu pot fi de fapt date . Un număr este de fapt dat dacă există un algoritm care vă permite să găsiți orice cifră a reprezentării sale zecimale pe care doriți să o găsiți. Un algoritm poate fi văzut ca o mașină Turing . În acest sens, conceptul de algoritm este eliminat din domeniul abstract și identificat cu ceva mai concret.

Caracteristici de calculabilitate

Există multe alte formulări despre ceea ce este un algoritm . Noțiunea de calculabilitate traduce riguros, prin noțiunea de funcție și noțiunea de algoritm, posibilitatea realizării unui anumit tip de sarcină sau rezolvării unui anumit tip de problemă prin aplicarea unei proceduri automate prestabilite. Este foarte important să știm dacă o anumită treabă poate fi realizată de o mașină sau de o persoană care nu poate lua decizii autonome sau dacă este necesară prezența unei persoane chemate să decidă de la caz la caz sau cel puțin în cele mai dificile riscuri de a face greșeli. Multe probleme pot fi rezolvate de mașini, dar există unele cunoscute care nu pot fi rezolvate de nicio mașină. Cel mai clasic exemplu de problemă care nu poate fi rezolvată automat este așa-numita problemă Stop .

Elemente conexe