Funcție calculabilă

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 model de calcul^⁠(d).

Au fost propuse multe astfel de modele de calcul, cele majore fiind mașinile Turing, mașinile cu regiștri^⁠(d), calculul lambda^⁠(d) și funcțiile general recursive^⁠(d). 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 exponențial^⁠(d) (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.

Axiomele Blum^⁠(d) 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 problemă funcție^⁠(d), 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 procedură efectivă^⁠(d). Mai riguros, o funcție $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ este calculabilă dacă există o procedură efectivă care, dat fiind orice $k$ -tuplu^⁠(d) $\mathbf {x}$ de numere naturale, va produce valoarea $f(\mathbf {x} )$ .^[1] Î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 modele de calcul^⁠(d) echivalente, inclusiv:

Mașini Turing
Funcții general recursive^⁠(d)
Calculul Lambda^⁠(d)
Mașini Post (mașini Post–Turing^⁠(d) și mașini de taguri^⁠(d)).
Mașini cu regiștri^⁠(d)

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ă.^[2] 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.^[3]^:6

De exemplu, se pot formaliza funcțiile calculabile ca funcții μ-recursive^⁠(d), care sunt funcții parțiale^⁠(d) care primesc tupluri^⁠(d) 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 compunerea^⁠(d), recursia primitivă^⁠(d), și operatorul μ^⁠(d).

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 mașină cu regiștri^⁠(d). Formal, o funcție parțială^⁠(d) $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ poate fi calculată dacă există un program de calculator cu următoarele proprietăți:

Dacă $f(\mathbf {x} )$ este definită, atunci programul se termină pe intrarea $\mathbf {x}$ cu valoarea $f(\mathbf {x} )$ stocată în memoria calculatorului.
Dacă $f(\mathbf {x} )$ nu este definită, atunci programul nu se termină pe intrarea $\mathbf {x}$ .

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 [1977] dă următoarele caracteristici ale unei proceduri pentru funcțiile calculabile; caracterizări similare au fost date de Turing [1936], Rogers [1967], ș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ă:

dacă i se dau date de intrare din domeniul ei, bazându-se posibil pe un spațiu de stocare nemărginit, poate produce rezultatul corespunzător urmând o procedură (program, algoritm) formată dintr-un număr finit de instrucțiuni exacte și neambigue;
produce acest rezultat (se oprește) într-un număr finit de pași; și
dacă primește date de intrare din afara domeniului, fie nu se oprește, fie se blochează.

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 $A$ de numere naturale se numește calculabilă^⁠(d) (sinonime: recursivă, decidabilă) dacă există o funcție totală calculabilă $f$ astfel încât pentru orice număr natural $n$ , $f (n) = 1$ dacă $n$ este în $A$ și $f (n) = 0$ dacă $n$ nu este în $A$ .

O submulțime a mulțimii numerelor naturale se numește recursiv enumerabilă^⁠(d) (sinonime: calculabil enumerabilă, semidecidabilă) dacă există o funcție calculabilă $f$ astfel încât, pentru fiecare număr $n$ , $f (n)$ este definită dacă și numai dacă $n$ 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ă $B$ a mulțimii numerelor naturale:

$B$ este domeniul unei funcții calculabile.
$B$ este codomeniul unei funcții totale calculabile. Dacă $B$ este infinită, atunci se poate presupune că funcția este injectivă.

Dacă o mulțime $B$ este codomeniul unei funcții $f$ , atunci funcția poate fi văzută ca o enumerare a lui $B$ , deoarece lista $f (0), f (1), ...$ va include toate elementele lui $B$ .

Deoarece orice relație finitară^⁠(d) 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 ${0, 1$ }. 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ă $f$ astfel încât pentru orice cuvânt $w$ din alfabet, $f (w) = 1$ dacă cuvântul aparține alfabetului și $f (w) = 0$ 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ă $f$ astfel încât $f (w)$ este definită dacă și numai dacă cuvântul $w$ 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 : N^k → N, f(n₁,...n_k) := n.
Adunarea f : N² → N, f(n₁,n₂) := n₁ + n₂
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, $\color {Blue}f\circ g$ ^⁠(d) dacă f este unară, max(f,g), min(f,g), $arg max ⁠(d) {y \leq f (x)}$ ș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 funcția Busy Beaver^⁠(d) Σ) 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

Articol principal: 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).
Nu s-a propus niciun model de calcul mai puternic care să fie considerat efectiv calculabil^⁠(d).

Teza Church–Turing este uneori utilizată în demonstrații pentru a justifica faptul că o funcție particulară este calculabilă dând o descriere concretă procedurii de calcul. Se permite aceasta deoarece se consideră că toate utilizările tezei pot fi scutite de greoiul proces de scriere a unei proceduri formale pentru funcție într-un anume model de calcul.

Demonstrabilitate

Dacă se dă o funcție (sau o mulțime), ar putea fi interesant nu doar dacă este calculabilă, ci dacă acest lucru se poate demonstra într-un anume sistem de demonstrații (de regulă aritmetica Peano de ordinul întâi). O funcție despre care se poate demonstra că este calculabilă se numește demonstrabil totală.

Mulțimea funcțiilor demonstrabil totale este recursiv enumerabilă^⁠(d): se pot enumera toate funcțiile demonstrabil totale prin enumerarea tuturor demonstrațiilor corespunzătoare. Aceasta se poate face enumerând toate demonstrațiile din sistemul de demonstrații și ignorându-le pe cele irelevante.

Relația funcțiilor definite recursiv

Într-o funcție definită printr-o definiție recursivă^⁠(d), fiecare valoare este definită printr-o formulă fixă de ordinul întâi compusă din valori anterior definite ale aceleiași funcții sau ale altor funcții, care pot fi și simple constante. O submulțime a acestora o constituie funcțiile primitiv recursive. Un alt exemplu este funcția Ackermann^⁠(d), care este definită recursiv, dar nu este primitiv recursivă.^[4]

Pentru ca definițiile de acest tip să evite circularitatea sau recursia infinită, este necesar ca apelurile recursive la aceeași funcție în cadrul unei definiții să fie cu argumente care să fie mai mici într-o bună cvasi-ordonare^⁠(d) pe domeniul funcției. De exemplu, pentru funcția Ackermann $A$ , oricând definiția lui $A(x,y)$ face referire la $A(p,q)$ , atunci $(p,q)<(x,y)$ în raport cu ordinea lexicografică^⁠(d) pe perechi de numere naturale. În acest caz, și în cazul funcțiilor primitiv recursive, buna ordonare este evidentă, dar unele relații de tip „se referă la” sunt netrivial de demonstrat ca având bune ordonări. Orice funcție definită recursiv într-o manieră bine ordonată este calculabilă: fiecare valoare poate fi calculată expandând un arbore de apeluri recursive la funcție, iar expansiunea trebuie să se termine după un număr finit de apeluri, deoarece altfel lema lui Kőnig^⁠(d) ar duce la un șir infinit de apeluri, încălcând prezumția de bună ordonare.

Note

↑ Enderton, Herbert (2002). A Mathematical Introduction to Logic (ed. Second). USA: Elsevier. p. 209. ISBN 0-12-238452-0.
↑ Enderton, Herbert (2002). A Mathematical Introduction to Logic (ed. Second). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.
↑ R. Soare, Computability and Recursion Arhivat în 31 martie 2022, la Wayback Machine. (1995). Accessed 9 November 2022.
↑ Péter, Rózsa (1935). „Konstruktion nichtrekursiver Funktionen”. Mathematische Annalen^⁠(d). 111: 42–60. doi:10.1007/BF01472200.

Bibliografie

Cutland, Nigel. Computability. Cambridge University Press, 1980.
Enderton, H.B.^⁠(d) Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
Rogers, H.^⁠(d) Theory of recursive functions and effective computation (McGraw–Hill 1967).
Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society^⁠(d), Series 2, Volume 42 (1937), p.230–265. Retipărit în M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.

[1] Enderton, Herbert (2002). A Mathematical Introduction to Logic (ed. Second). USA: Elsevier. p. 209. ISBN 0-12-238452-0.

[2] Enderton, Herbert (2002). A Mathematical Introduction to Logic (ed. Second). USA: Elsevier. p. 208,262. ISBN 0-12-238452-0.

[3] R. Soare, Computability and Recursion Arhivat în 31 martie 2022, la Wayback Machine. (1995). Accessed 9 November 2022.

[4] Péter, Rózsa (1935). „Konstruktion nichtrekursiver Funktionen”. Mathematische Annalen^⁠(d). 111: 42–60. doi:10.1007/BF01472200.

[1]

[2]

[3]

[4]