Funcție calculată

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 10 aprilie 2019; verificarea necesită 1 editare .

Funcțiile calculabile sunt setul de funcții de formă care pot fi implementate pe o mașină Turing . Sarcina de a calcula o funcție se numește algoritmic determinabilă sau algoritmic indecidabilă , în funcție de dacă algoritmul care calculează această funcție este posibil. $f\coloană N\la N,$ $f$

Ca set , un set este de obicei considerat - un set de cuvinte din alfabetul binar , cu condiția ca rezultatul calculului să fie nu numai un cuvânt, ci și o valoare specială "incertitudine", corespunzătoare cazului în care algoritmul „se blochează”. Astfel, se poate da următoarea definiție : $N$ $B^{*}$ $B=\{0,1\}$ $N$

$N=B^{*}\cup \{\operatorname {undef} \},$

unde , a este un element special care denotă incertitudine. $B=\{0,1\}$ $\operatorname {undef}$

Rolul unei mulțimi poate fi jucat de mulțimea numerelor naturale, la care se adaugă elementul , iar apoi funcțiile calculabile sunt un subset de funcții cu valori naturale ale argumentului natural. Este convenabil să presupunem că diferite mulțimi numărabile pot acționa ca mulțime - mulțimea numerelor naturale, mulțimea numerelor raționale, mulțimea cuvintelor dintr-un alfabet finit etc. Este important să existe un limbaj formal în finit. alfabet pentru descrierea elementelor mulţimii şi că s-a calculat problema recunoaşterii corecte. De exemplu, pentru a descrie numerele naturale, este convenabil să folosiți sistemul de numere binar - limbajul pentru descrierea numerelor naturale în alfabet . $N$ $\operatorname {undef}$ $N$ $N$ $B$

În această definiție, în locul unui executant de mașină Turing, poate fi luat unul dintre executanții Turing-compleți . În linii mari, „executorul de referință” poate fi un computer abstract, asemănător cu computerele personale folosite, dar cu memorie potențial infinită și caracteristici arhitecturale care permit utilizarea acestei memorie infinite.

Este important de reținut că setul de programe pentru acest executor (de exemplu, setul de mașini Turing cu un alfabet fix de date de intrare și de ieșire) este numărabil . Prin urmare, setul de funcții calculabile este cel mult numărabil, în timp ce setul de funcții din formă este nenumărabil, dacă este numărabil. Aceasta înseamnă că există funcții necalculabile, iar cardinalitatea mulțimii lor este mai mare decât cardinalitatea mulțimii de funcții calculabile. Un exemplu de funcție necalculabilă (problema de nerezolvată din punct de vedere algoritmic) poate fi o funcție de detectare a opririi - o funcție care primește o descriere a unei mașini Turing și o intrare pentru aceasta ca intrare și returnează 0 sau 1, în funcție de dacă această mașină se oprește la o intrare dată sau nu. Un alt exemplu de funcție necalculabilă este complexitatea Kolmogorov . $f\coloană N\la N,$ $N$

Istorie

Înțelegerea că unele funcții ale formei sunt calculabile, iar altele nu, a apărut chiar înainte de apariția primelor calculatoare. Teoria computabilității provine din disertația lui Turing ( 1936 ), în care a introdus conceptul de computer abstract și funcțiile care sunt calculabile pe acesta. Pe măsură ce teoria computabilității s-a dezvoltat , au fost formulate mai multe definiții, care, după cum sa dovedit mai târziu, definesc același set de funcții - setul de funcții calculabile: $f\colon B^{*}\la B^{*}$

funcții implementate pe mașinile Turing ( Alan Turing );
funcții implementate pe algoritmi Markov normali ( A. A. Markov );
funcții implementate pe mașina Postului ;
funcții parțial recursive ( Kurt Gödel , Stephen Kleene );
funcții implementate pe o mașină de registre .

Vezi și

teza Church-Turing
Turing completitatea
Funcții parțial recursive
Funcții recursive generale
Funcții recursive primitive
Seturi Rezolvabile
Seturi enumerate
Funcții necalculabile ( probleme nerezolvabile din punct de vedere algoritmic ):

Opriți problema
Problema de echivalență a algoritmului
Problema de a dovedi adevărul sau falsitatea unei afirmații
A zecea problemă a lui Hilbert - Rezolvarea unei ecuații diofantine în numere întregi
Auto-aplicabilitate

Link -uri

Cursuri de calculabilitate