MARC Record from harvard_bibliographic_metadata

LEADER: 03637pam a2200349 a 4500
001 000416910-7
005 20020606090541.3
008 820429r19821958nyu b 00110 eng
010 $a 82007287
020 $a0486614719 (pbk.)
035 0 $aocm08475039
040 $aDLC$cDLC
050 00 $aQA9.615$b.D38 1982
100 1 $aDavis, Martin,$d1928-
245 10 $aComputability & unsolvability /$cMartin Davis.
246 3 $aComputability and unsolvability.
250 $aDover ed.
260 0 $aNew York :$bDover,$c1982.
300 $axxv, 248 p. ;$c22 cm.
500 $aReprint. Originally published: New York : (McGraw-Hill, 1958. McGraw-Hill series in information processing and computers. With new pref. and appendix)
500 $aIncludes index.
504 $aBibliography: p. 237-241.
505 0 $aIntroduction -- Heuristic remarks on decision problems -- Suggestions to the reader -- Notational conventions -- Part I. The General Yheory of Computability -- Computable functions -- Turing Machines -- Computable functions and partially computable functions -- Some examples -- Relatively computable functions -- Operations on computable functions -- Preliminary lemmas -- Composition and minimalization -- Recursive functions -- Some classes of functions -- Finite sequences of natural numbers -- Primitive recursion -- Primitive recursive functions -- Recursive sets and predicates -- Turing machines self-applied -- Arithmetization of the theory of turing machines -- Computability and recursiveness -- A universal turing machine -- Unsolvable decision problems -- Semicomputable predicates -- Decision problems -- Properties of semicomputable predicates -- Recursively enumerable sets -- Two recursively enumerable sets -- A set which is not recursively enumerable --
505 0 $aPart 2. Applications of the General Theory -- Combinatorial problems -- Combinatorial systems -- Turing machines and semi-thue systems -- Thue systems -- The word problem for semigroups -- Normal systems and post systems -- Diophantine equations -- Hilbert's tenth problem -- Arithmetical and diophantine predicates -- Arithmetical representation of semicomputable predicates -- Mathematical logic -- Logics -- Incompleteness and unsolvability theorems for logics -- Arithmetical logics -- First-order logics -- Partial propositional calculi -- Part 3. Further Development of the General Theory -- The Kleene hierarchy -- The interation theorem -- Some first applications of the iteration theorem -- Predicates, sets, and functions -- Strong reducibility -- Some classes of predicates -- A representation theorem for P subscript 2 superscript A -- Post's representation theorem -- Computable functionals -- Functionals -- Complete computable functionals -- Normal form theorems --
505 0 $aPartially computable and computable functionals -- Functionals and relative recursiveness -- Decision problems -- The recursion theorems -- The classification of unsolvable decision problems -- Reducibility and the Kleene hierarchy -- Incomparability -- Creative sets and simple sets -- Constructive ordinals -- Extensions of the Kleene hierarchy -- Appendix 1. Some results from the elementary theory of numbers -- Appendix 2. Hilbert's tenth problem is unsolvable.
650 0 $aRecursive functions.
650 0 $aUnsolvability (Mathematical logic)
650 0 $aComputable functions.
776 08 $iOnline version:$aDavis, Martin, 1928-$tComputability & unsolvability.$bDover ed.$dNew York : Dover, 1982$w(OCoLC)565053613
830 0 $aMcGraw-Hill series in information processing and computers.
988 $a20020608
906 $0DLC