Funcțiile calculabile sunt obiectul elementar al studiului teoriei calculabilității. Intuitiv, o funcție este calculabilă dacă există un algoritm care calculează valoarea funcției pentru orice valoare a argumentului ei. Din lipsa unei definiții exacte a conceptului de algoritm, orice definiție formală a calculabilității trebuie să facă referire la un anume .
Au fost propuse multe astfel de modele de calcul, cele majore fiind mașinile Turing, , și . Deși acestea patru au naturi foarte diferite între ele, ele oferă exact aceeași clasă de funcții calculabile, și, pentru orice model de calcul care a fost propus vreodată, funcțiile calculabile pentru un astfel de model sunt calculabile șî pentru cele patru modele de calcul de mai sus.
Teza Church–Turing este aserțiunea nedemonstrabilă că toate noțiunile de calculabilitate care pot fi imaginate pot calcula doar funcții calculabile în sensul de mai sus.
Înainte de definiția precisă a funcțiilor calculabile, matematicienii foloseau adesea termenul informal efectiv calculabilă. Acest termen a fost identificat de atunci cu funcțiile calculabile. Calculabilitatea efectivă a acestor funcții nu implică și că ar putea fi calculate eficient (adică calculate într-o perioadă de timp rezonabilă). De fapt, pentru unele funcții efectiv calculabile, se poate arăta că orice algoritm care le calculează va fi foarte ineficient, în sensul că timpul de rulare al algoritmului crește (sau chiar supraexponențial) cu lungimea intrării. Domeniile calculabilității fezabile și al complexității computaționale studiază funcții care pot fi calculate eficient.
pot fi folosite pentru a defini o teorie abstractă a complexității pe mulțimea funcțiilor calculabile. În teoria complexității, problema calculului valorii unei funcții este cunoscut ca , pentru a o deosebi de o problemă de decizie ale cărei rezultate sunt pot fi doar „da” sau „nu”.
Definiție Calculabilitatea unei funcții este o noțiune informală. Un mod de a o descrie este a spune că o funcție este calculabilă dacă valoarea ei se poate obține printr-o . Mai riguros, o funcție este calculabilă dacă există o procedură efectivă care, dat fiind orice - de numere naturale, va produce valoarea . În conformitate cu această definiție, restul acesui articol prezumă că funcțiile calculabile primesc un număr finit de numere naturale ca argumente și produc o valoare care este un singur număr natural.
Pe lângă această descriere informală, există mai multe definiții formale, matematice. Clasa funcțiilor calculabile pot fi definite în mai multe echivalente, inclusiv:
Mașini Turing
Mașini Post ( și ).
Deși aceste modele folosesc reprezentări diferite pentru funcții, intrări și ieșiri, există traduceri între cele două modele, și deci fiecare model descrie în esență aceeași clasă de funcții, dând naștere opiniei că calculabilitatea formală este naturală și nu foarte restrânsă. Aceste funcții sunt uneori denumite „recursive", spre deosebire de termenul informal „calculabile”, o distincție care își are sursa în discuția din 1934 între Kleene și Gödel.R. Soare, Computability and Recursion (1995). Accessed 9 November 2022.
De exemplu, se pot formaliza funcțiile calculabile ca , care sunt care primesc finite de numere naturale și returnează un singur număr natural (ca și mai sus). Ele reprezintă cea mai restrânsă clasă de funcții parțiale, care includ funcția constantă, funcția succesor și funcția proiecție, și este închisă în raport cu , , și .
Echivalent, funcțiile calculabile pot fi formalizate ca funcții ce pot fi calculate printr-un agent idealizat de calcul, cum ar fi mașina Turing sau o . Formal, o poate fi calculată dacă există un program de calculator cu următoarele proprietăți:
Dacă este definită, atunci programul se termină pe intrarea cu valoarea stocată în memoria calculatorului. Dacă nu este definită, atunci programul nu se termină pe intrarea .
Caracteristicile funcțiilor calculabile Caracteristica de bază a unei funcții calculabile este acceea că trebuie să existe o procedură finită (un algoritm) care să descrie cum se calculează funcția. Modelele de calcul enumerate mai sus dau diferite implementări ale conceptului de procedură, și a felului cum se folosește, dar aceste interpretări au în comun multe proprietăți. Faptul că aceste modele dau clase echivalente de funcții calculabile rezultă din faptul că fiecare model este capabil de a citi și de a imita o procedură a oricărui alt model, la fel cum un compilator poate citi instrucțiuni într-un limbaj de programare pentru a emite instrucțiuni în alt limbaj.
Enderton dă următoarele caracteristici ale unei proceduri pentru funcțiile calculabile; caracterizări similare au fost date de Turing , Rogers , și alții.
„Trebuie să existe instrucțiuni precise (un program), de lungime finită, pentru procedură.” Astfel, orice funcție calculabilă trebuie să aibă un program finit care descrie complet cum se calculează ea. Trebuie să se poată calcula funcția doar urmând acele instrucțiuni; nu trebuie să fie nevoie de intuiție sau de informații speciale. „Dacă procedura primește un k-tuplu x din domeniul lui f, atunci procedura trebuie să se termine și să produă f(x) într-un număr finit de pași.” Intuitiv, procedura lucrează pas cu pas, cu o regulă specială care descrie ce trebuie făcut la fiecare pas de calcul. Se poate executa doar un număr finit de pași după care trebuie returnată valoarea funcției. „Dacă procedura primește un k-tuplu x care nu este din domeniul lui f, atunci procedura poate să ruleze la nesfârșit, fără să se oprească, sau să se blocheze la un moment dat (ca de exemplu la o instrucțiune ce nu poate fi executată), dar nu trebuie să pretindă că produce o valoarea lui f în x.” Astfel, dacă se găsește o valoare pentru f(x), ea trebuie să fie cea corectă. Nu este nevoie ca agentul de calcul să facă distincția între rezultatele corecte și cele incorecte, deoarece procedura este definită ca fiind corectă dacă și numai dacă produce un rezultat.
Enderton enumeră și câteva clarificări ale acestor trei condiții puse asupra procedurii pentru o funcție calculabilă:
Procedura trebuie să funcționeze teoretic pentru argumente arbitrar de mari. De exemplu, nu se face presupunerea că argumentele ar fi mai mici decât numărul atomilor de pe Pământ. Procedura trebuie să se oprească după un număr finit de pași după care produce un rezultat, dar poate rula un număr arbitrar de pași înainte să se oprească. Nu se face nicio presupunere despre vreo limitare în timp. Deși procedura poate folosi doar o cantitate finită de spațiu într-o rulare reușită, nu există vreo limită asupra cantității de spațiu folosite. Se presupune că procedurii i se poate pune la dispoziție spațiu de stocare adițional în cazul în care îl cere.
Pe scurt, pe baza acestei perspective, o funcție este calculabilă dacă:Domeniul teoriei complexității studiază funcțiile care au limite prescrise asupra timpului și/sau spațiului folosit la o rulare reușită.
Mulțimi și relații calculabile O mulțime de numere naturale se numește (sinonime: recursivă, decidabilă) dacă există o funcție totală calculabilă astfel încât pentru orice număr natural , dacă este în și dacă nu este în .
O submulțime a mulțimii numerelor naturale se numește (sinonime: calculabil enumerabilă, semidecidabilă) dacă există o funcție calculabilă astfel încât, pentru fiecare număr , este definită dacă și numai dacă aparține mulțimii. Deci, o mulțime este recursiv enumerabilă dacă și numai dacă este domeniul unei funcții calculabile. Se folosește cuvântul enumerabilă deoarece următoarele sunt echivalente pentru o submulțime nevidă a mulțimii numerelor naturale:
este domeniul unei funcții calculabile. este codomeniul unei funcții totale calculabile. Dacă este infinită, atunci se poate presupune că funcția este injectivă.
Dacă o mulțime este codomeniul unei funcții , atunci funcția poate fi văzută ca o enumerare a lui , deoarece lista va include toate elementele lui .
Deoarece orice definită pe mulțimea numerelor naturale poate fi identificată cu o mulțime corespunzătoare de numere naturale, se pot defini noțiunile de relație calculabilă și relație recursiv enumerabilă analog cu cele definite pe mulțimi.
Limbaje formale În teoria calculabilității din informatică, se consideră adesea limbajele formale. Un alfabet este o mulțime arbitrară. Un cuvânt definit pe un alfabet este un șir finit de simboluri din alfabet; același simbol se poate folosi de mai multe ori. De exemplu, șirurile binare sunt exact cuvintele peste alfabetul }. Un limbaj este o submulțime a colecției tuturor cuvintelor peste un alfabet fixat. De exemplu, colecția tuturor șirurilor binare ce conțin exact trei simboluri 1 este un limbaj peste alfabetul binar.
O proprietate-cheie a unui limbaj formal este nivelul de dificultate necesar pentru a decide dacă un cuvânt dat aparține limbajului. Trebuie dezvoltat un sistem de codare pentru a permite unei funcții calculabile să primească un cuvânt arbitrar din limbaj ca intrare. Un limbaj se numește calculabil (sinonime: recursiv, decidabil) dacă există o funcție calculabilă astfel încât pentru orice cuvânt din alfabet, dacă cuvântul aparține alfabetului și dacă nu aparține. Astfel, un limbaj este calculabil dacă există o procedură ce poate determina corect dacă un cuvânt arbitrar aparține sau nu limbajului.
Un limbaj este recursiv enumerabil (sinonime: recursiv calculabil, semidecidabil) dacă există o funcție calculabilă astfel încât este definită dacă și numai dacă cuvântul aparține limbajului. Termenul enumerabil are aceeași etimologie ca la mulțimile recursiv enumerabile de numere naturale.
Exemple Următoarele funcții sunt calculabile:
Orice funcție cu domeniul finit; de exemplu, orice șir finit de numere naturale. Orice funcție constantă f : Nk → N, f(n1,...nk) := n. Adunarea f : N2 → N, f(n1,n2) := n1 + n2 Cel mai mare divizor comun a două numere Coeficientul Bézout a două numere Cel mai mic factor prim al unui număr
Dacă f și g sunt calculabile, atunci sunt calculabile și: f + g, f * g, dacă f este unară, max(f,g), min(f,g), și multe alte astfel de combinații.
Următoarele exemple ilustrează faptul că o funcție poate fi calculabilă chiar dacă nu i se cunoaște algoritmul care o calculează.
Funcția f astfel încât f(n) = 1 dacă există un șir de cel puțin n cifre de cinci consecutive în scrierea zecimală a numărului π, și f(n) = 0 altfel, este calculabilă. (Funcția f este fie funcția constantă 1, care este calculabilă, fie există un k astfel încât f(n) = 1 dacă n < k și f(n) = 0 dacă n ≥ k. Orice astfel de funcție este calculabilă. Nu se știe dacă există șiruri arbitrar de lungi de cifre de 5 în scrierea zecimală a lui π, așa că nu știm care din aceste funcții este f. Știm însă că f este cu siguranță calculabilă.) Fiecare segment finit dintr-un șir necalculabil de numere naturale (cum ar fi Σ) este calculabilă. De exemplu, pentru orice număr natural n, există un algoritm care calculează șirul finit Σ(0), Σ(1), Σ(2), ..., Σ(n) — spre deosebire de faptul că nu există niciun algoritm care să calculeze întregul șir Σ, adică Σ(n) pentru orice n. Astfel, „Tipărește 0, 1, 4, 6, 13” este un algoritm trivial de calcul pentru Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similar, pentru orice valoare dată a lui n, există un astfel de algoritm trivial (deși probabil nu va fi cunoscut sau produs de cineva vreodată) pentru a calcula Σ(0), Σ(1), Σ(2), ..., Σ(n).
Teza Church–Turing
Teza Church–Turing afirmă că orice funcție calculabilă printr-o procedură ce are cele trei proprietăți enumerate mai sus este o funcție calculabilă. Deoarece aceste trei proprietăți nu sunt enunțate formal, teza Church–Turing nu poate fi demonstrată. Pentru a susține ideea tezei, sunt luate ca indicii următoarele fapte:
Se cunosc multe modele echivalente de calcul, și toate dau aceeași definiție unei funcții calculabile (sau o versiune mai slabă, în unele cazuri).