Beregnelighedsteori

Teorien om beregningsevne , også kendt som teorien om rekursive funktioner, er en gren af ​​moderne matematik , der ligger i krydsfeltet mellem matematisk logik , teorien om algoritmer og datalogi , som opstod som et resultat af at studere begreberne beregnelighed og ikke -beregnelighed. Oprindeligt var teorien viet til beregnelige og ikke-beregnelige funktioner og sammenligning af forskellige beregningsmodeller . Nu er studieområdet for beregningsbarhedsteorien udvidet - nye definitioner af begrebet beregnelighed dukker op, og der er en fusion med matematisk logik, hvor vi i stedet for beregnelighed og ikke-beregnelighed taler om bevisbarhed og ikke-bevisbarhed (deducerbarhed og ikke-udledbarhed) af udsagn inden for rammerne af eventuelle teorier.

Teorien om beregningsevne stammer fra Alan Turings ( 1936 ) arbejde "On Computable Numbers, With An Application to Entscheidungsproblem", hvori han introducerede begrebet en abstrakt computer, som senere fik hans navn, og beviste den grundlæggende sætning om uløselighed af problemet med at stoppe det . Gödels berømte ufuldstændighedssætning ( 1931 ) blev bevist i form af primitive rekursive funktioner , hvis klasse Gödel udvidede i 1934 til klassen af ​​generelle rekursive funktioner . Den formalisme, som Gödel udviklede, viste sig at svare til Turings (såvel som mange andre). Sammen med Church-Turing-afhandlingen demonstrerede dette faktum tydeligt indholdet af den nye teori, og nu er disse definitioner generelt accepteret som en formel analog af algoritmisk beregnelige funktioner.

Gödels definition af beregnbare funktioner var af syntaktisk karakter, og kun etableringen af ​​denne klasses sammenfald med klassen af ​​generelle rekursive funktioner (sammen med formuleringen og "accepten" af Kirkens tese) viste den reelle betydning af ufuldstændighedsteoremet.Ershov, Yuri Leonidovich

Se også

• Rice's teorem
• Stop problemet

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

Litteratur

• Boolos J., Jeffrey R. Beregnelighed og logik. — M .: Mir, 1994. — 396 s.
• Ershov Yu.L. Nummereringsteori. — M .: Nauka, 1977. — 416 s.
• Cutland N. Beregnelighed. Introduktion til teorien om rekursive funktioner - M. : Mir, 1986. - 256 s.
• Kleene. Introduktion til metamatematik. - M . : Forlag for udenlandsk litteratur, 1957. - 526 s.
• Maltsev A.I. Algoritmer og rekursive funktioner. - M. : Nauka, 1965. - 392 s.
• Manin Yu.I. Beregnbar og ikke-beregnerbar. - M . : Sovjetisk radio, 1980. - 128 s.
• Minsky M. Beregninger og automater. - M . : Mir, 1971. - 366 s.
• Hodgers H. Teori om rekursive funktioner og effektiv beregnelighed. - M . : Mir, 1972. - 624 s.
• Barweis J. En opslagsbog om matematisk logik i fire dele. Del III. Teori om rekursion .. - M . : Nauka, 1982. - 360 s.
• Uspensky V.A. Forelæsninger om beregnelige funktioner. - M. : Fizmatgiz, 1960. - 492 s.
• Uspensky V.A., Semenov L.A. Algoritmerteori: vigtigste opdagelser og anvendelser. — M .: Nauka, 1987.
• Shenfield J. Grader af uafgørelighed. — M .: Nauka, 1977. — 192 s.

Links