Teoria computabilității

Teoria computabilității , cunoscută și sub denumirea de teoria funcțiilor recursive, este o ramură a matematicii moderne care se află la intersecția dintre logica matematică , teoria algoritmilor și informatica , care a apărut ca urmare a studierii conceptelor de computabilitate și non -computabilitate. Inițial, teoria a fost dedicată funcțiilor calculabile și necalculabile și comparării diferitelor modele de calcul . Acum domeniul de studiu al teoriei computabilității s-a extins - apar noi definiții ale conceptului de computabilitate și are loc o fuziune cu logica matematică, unde în loc de calculabilitate și non-computabilitate, vorbim despre demonstrabilitatea și nedemonstrabilitatea (deductibilitatea și nederivabilitatea) enunțurilor în cadrul oricăror teorii.

Teoria computabilității provine din lucrarea lui Alan Turing ( 1936 ) „On Computable Numbers, With An Application to Entscheidungsproblem”, în care a introdus conceptul de computer abstract, care mai târziu a primit numele și a demonstrat teorema fundamentală despre imposibilitatea de rezolvare a problemei opririi ei . Celebra teoremă de incompletitudine a lui Gödel ( 1931 ) a fost demonstrată în termeni de funcții recursive primitive , a căror clasă Gödel a extins -o în 1934 la clasa funcțiilor recursive generale . Formalismul dezvoltat de Gödel s-a dovedit a fi echivalent cu cel al lui Turing (ca și cu multe altele). Împreună cu teza Church-Turing, acest fapt a demonstrat în mod clar conținutul noii teorii, iar acum aceste definiții sunt în general acceptate ca un analog formal al funcțiilor calculabile algoritmic.

Definiția lui Gödel a funcțiilor calculabile a fost de natură sintactică și doar stabilirea coincidenței acestei clase cu clasa funcțiilor recursive generale (împreună cu formularea și „acceptarea” tezei lui Church) a arătat semnificația reală a teoremei incompletității.Ershov, Yuri Leonidovici

Vezi și

• Teorema lui Rice
• Opriți problema

• Kurt Gödel
• Alan Turing
• Stephen Kleene
• Biserica Alonzo
• Emil Post

Literatură

• Boolos J., Jeffrey R. Calculabilitate și logică. — M .: Mir, 1994. — 396 p.
• Ershov Yu.L. Teoria numerotatii. — M .: Nauka, 1977. — 416 p.
• Cutland N. Calculabilitate. Introducere în teoria funcţiilor recursive - M. : Mir, 1986. - 256 p.
• Kleene. Introducere în metamatematică. - M . : Editura de literatură străină, 1957. - 526 p.
• Maltsev A.I. Algoritmi și funcții recursive. - M. : Nauka, 1965. - 392 p.
• Manin Yu.I. Calculabil și necalculabil. - M . : Radio sovietică, 1980. - 128 p.
• Minsky M. Calcule și automate. - M . : Mir, 1971. - 366 p.
• Hodgers H. Teoria funcţiilor recursive şi calculabilitatea efectivă. - M . : Mir, 1972. - 624 p.
• Barweis J. O carte de referință despre logica matematică în patru părți. Partea a III-a. Teoria recursiunii .. - M . : Nauka, 1982. - 360 p.
• Uspensky V.A. Prelegeri despre funcții calculabile. - M. : Fizmatgiz, 1960. - 492 p.
• Uspensky V.A., Semenov L.A. Teoria algoritmilor: principalele descoperiri si aplicatii. — M .: Nauka, 1987.
• Shenfield J. Grade de indecidibilitate. — M .: Nauka, 1977. — 192 p.

Link -uri