Kiszámíthatóság elmélet

A kiszámíthatóság elmélete , más néven a rekurzív függvények elmélete, a modern matematikának egy olyan ága, amely a matematikai logika , az algoritmusok elmélete és a számítástechnika találkozásánál fekszik, és amely a kiszámíthatóság és a nem fogalmak tanulmányozása eredményeként jött létre. - kiszámíthatóság. Kezdetben az elméletet a kiszámítható és nem kiszámítható függvényeknek, valamint a különböző számítási modellek összehasonlításának szentelték . Mostanra kibővült a kiszámíthatóság elméletének tudományterülete - a kiszámíthatóság fogalmának új definíciói jelennek meg, és összeolvad a matematikai logikával , ahol a kiszámíthatóság és a nem kiszámíthatóság helyett bizonyíthatóságról és nem bizonyíthatóságról (levezethetőségről és nem) beszélünk. -levezethetőség) bármely elmélet keretein belüli állítások.

A kiszámíthatóság elmélete Alan Turing ( 1936 ) "On Computable Numbers, With An Application to Entscheidungsproblem" című munkájából származik , amelyben bevezette az absztrakt számítógép fogalmát, amely később a nevét kapta, és bebizonyította az alapvető tételt a a megállítás problémájának megoldhatatlansága . Gödel híres befejezetlenségi tételét ( 1931 ) a primitív rekurzív függvényekkel igazolták , amelynek osztályát Gödel 1934 -ben kiterjesztette az általános rekurzív függvények osztályára . A Gödel által kidolgozott formalizmus egyenértékűnek bizonyult Turingével (és sok mással is). Ez a tény a Church-Turing-tézissel együtt egyértelműen megmutatta az új elmélet tartalmát, és ma már általánosan elfogadottak ezek a definíciók az algoritmikusan kiszámítható függvények formális analógjaként.

Gödel definíciója a kiszámítható függvényekre szintaktikai jellegű volt, és csak ennek az osztálynak az egybeesésének megállapítása az általános rekurzív függvények osztályával (együtt Church tézisének megfogalmazásával és „elfogadásával”) mutatta meg a hiányossági tétel valódi jelentőségét.Ershov, Jurij Leonidovics

Lásd még

• Rice tétele
• Állítsa le a problémát

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

Irodalom

• Boolos J., Jeffrey R. Kiszámíthatóság és logika. — M .: Mir, 1994. — 396 p.
• Ershov Yu.L. Számozáselmélet. — M .: Nauka, 1977. — 416 p.
• Cutland N. Kiszámíthatóság . Bevezetés a rekurzív függvények elméletébe - M. : Mir, 1986. - 256 p.
• Kleene. Bevezetés a metamatematikába. - M . : Külföldi Irodalmi Kiadó, 1957. - 526 p.
• Maltsev A.I. Algoritmusok és rekurzív függvények. - M. : Nauka, 1965. - 392 p.
• Manin Yu.I. Kiszámítható és nem számítható. - M . : Szovjet rádió, 1980. - 128 p.
• Minsky M. Számítások és automaták. - M . : Mir, 1971. - 366 p.
• Hodgers H. A rekurzív függvények elmélete és a hatékony kiszámíthatóság. - M . : Mir, 1972. - 624 p.
• Barweis J. Négy részből álló kézikönyv a matematikai logikáról. rész III. A rekurzió elmélete .. - M . : Nauka, 1982. - 360 p.
• Uszpenszkij V.A. Előadások a kiszámítható függvényekről. - M. : Fizmatgiz, 1960. - 492 p.
• Uspensky V.A., Semenov L.A. Algoritmusok elmélete: főbb felfedezések és alkalmazások. - M .: Nauka, 1987.
• Shenfield J. A eldönthetetlenség fokai. — M .: Nauka, 1977. — 192 p.

Linkek