Funcție calculabilă

Această intrare sau secțiune despre matematică nu citează sursele necesare sau cei prezenți sunt insuficienți . Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor . Urmați sfaturile de proiectare de referință .

Funcțiile calculabile sunt principalul obiect de studiu al teoriei calculabilității . Funcțiile calculabile sunt analogul formal al noțiunii intuitive de algoritm , în sensul că o funcție este calculabilă dacă există un algoritm care poate îndeplini sarcina funcției în sine, adică dacă i se dă o intrare din domeniul funcției, aceasta este capabilă să returneze ieșirea corespunzătoare.

Conform tezei Church-Turing (care nu a fost încă dovedită), funcțiile calculabile corespund funcțiilor recursive și, prin urmare, tuturor modelelor de calcul echivalente .

Proprietate

O funcție calculabilă este în general o funcție parțială

${\displaystyle \mathrm{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">f</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">:</span></span>\mathbb{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">\to </span></span>\mathbb{<span\; class="mwe-math-element"><span\; class="mwe-math-mathml-inline\; mwe-math-mathml-a11y"\; style="display:\; none;">Nu.</span></span>}}${\ displaystyle f: \ mathbb {N} \ to \ mathbb {N}}

Conform tezei Church-Turing (nedemonstrabilă), clasa funcțiilor calculabile este echivalentă cu clasa funcțiilor definite de

• funcții recursive
• Calculul lambda al Bisericii
• algoritmii normali Markov

Alternativ, ele pot fi definite ca algoritmii calculabili de

• mașinile Turing
• sistemele combinatorii ale Post
• mașini de înregistrare primare

Elemente conexe

• Echivalența Turing

linkuri externe

• ( EN )Funcție calculabilă , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică