Beräkningsbarhetsteori

Teorin om beräkningsbarhet , även känd som teorin om rekursiva funktioner, är en gren av modern matematik som ligger i korsningen mellan matematisk logik , teorin om algoritmer och datavetenskap , som uppstod som ett resultat av att studera begreppen beräkningsbarhet och icke -beräknebarhet. Till en början ägnades teorin åt beräkningsbara och icke beräkningsbara funktioner och jämförelse av olika beräkningsmodeller . Nu har studieområdet för beräkningsbarhetsteorin utökats - nya definitioner av begreppet beräkningsbarhet dyker upp och det sker en sammanslagning med matematisk logik, där vi istället för beräkningsbarhet och icke-beräknelighet talar om bevisbarhet och opåvisbarhet (deducerbarhet och icke-deriverbarhet) av påståenden inom ramen för eventuella teorier.

Teorin om beräkningsbarhet härstammar från arbetet av Alan Turing ( 1936 ) "On Computable Numbers, With An Application to Entscheidungsproblem", där han introducerade konceptet med en abstrakt dator, som senare fick hans namn, och bevisade den grundläggande satsen om olöslighet av problemet med att stoppa det . Gödels berömda ofullständighetsteorem ( 1931 ) bevisades i termer av primitiva rekursiva funktioner , vars klass Gödel utvidgades 1934 till klassen av allmänna rekursiva funktioner . Den formalism som utvecklats av Gödel visade sig vara likvärdig med Turings (liksom många andra). Tillsammans med Church-Turing-avhandlingen visade detta faktum tydligt innehållet i den nya teorin, och nu är dessa definitioner allmänt accepterade som en formell analog av algoritmiskt beräkningsbara funktioner.

Gödels definition av beräkningsbara funktioner var av syntaktisk karaktär, och endast fastställandet av sammanträffandet av denna klass med klassen av allmänna rekursiva funktioner (tillsammans med formuleringen och "acceptansen" av kyrkans avhandling) visade den verkliga betydelsen av ofullständighetsteoremet.Ershov, Yuri Leonidovich

Se även

• Rice's teorem
• Sluta problem

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

Litteratur

• Boolos J., Jeffrey R. Beräkningsbarhet och logik. — M .: Mir, 1994. — 396 sid.
• Ershov Yu.L. Numreringsteori. — M .: Nauka, 1977. — 416 sid.
• Cutland N. Beräkningsbarhet. Introduktion till teorin om rekursiva funktioner - M. : Mir, 1986. - 256 sid.
• Kleene. Introduktion till metamatematik. - M . : Förlag för utländsk litteratur, 1957. - 526 sid.
• Maltsev A.I. Algoritmer och rekursiva funktioner. - M. : Nauka, 1965. - 392 sid.
• Manin Yu.I. Beräkningsbar och icke beräkningsbar. - M . : Sovjetisk radio, 1980. - 128 sid.
• Minsky M. Beräkningar och automater. - M . : Mir, 1971. - 366 sid.
• Hodgers H. Teori om rekursiva funktioner och effektiv beräkningsbarhet. - M . : Mir, 1972. - 624 sid.
• Barweis J. En uppslagsbok om matematisk logik i fyra delar. Del III. Theory of recursion .. - M . : Nauka, 1982. - 360 sid.
• Uspensky V.A. Föreläsningar om beräkningsbara funktioner. - M. : Fizmatgiz, 1960. - 492 sid.
• Uspensky V.A., Semenov L.A. Algoritmteori: huvudsakliga upptäckter och tillämpningar. — M .: Nauka, 1987.
• Shenfield J. Grader av obeslutlighet. — M .: Nauka, 1977. — 192 sid.

Länkar