001448610 000__ 04012cam\a2200481\a\4500
001448610 001__ 1448610
001448610 003__ OCoLC
001448610 005__ 20230310004247.0
001448610 006__ m\\\\\o\\d\\\\\\\\
001448610 007__ cr\un\nnnunnun
001448610 008__ 220813s2022\\\\sz\\\\\\ob\\\\001\0\eng\d
001448610 019__ $$a1338643128
001448610 020__ $$a9783030832025$$q(electronic bk.)
001448610 020__ $$a3030832023$$q(electronic bk.)
001448610 020__ $$z9783030832018
001448610 020__ $$z3030832015
001448610 0247_ $$a10.1007/978-3-030-83202-5$$2doi
001448610 035__ $$aSP(OCoLC)1338838684
001448610 040__ $$aEBLCP$$beng$$epn$$cEBLCP$$dGW5XE$$dOCLCQ$$dYDX$$dOCLCF$$dUKAHL$$dOCLCQ
001448610 049__ $$aISEA
001448610 050_4 $$aQA9.59
001448610 08204 $$a511.3/52$$223/eng/20220816
001448610 1001_ $$aTourlakis, George J.
001448610 24510 $$aComputability /$$cGeorge Tourlakis.
001448610 260__ $$aCham :$$bSpringer,$$c2022.
001448610 300__ $$a1 online resource (652 pages)
001448610 336__ $$atext$$btxt$$2rdacontent
001448610 337__ $$acomputer$$bc$$2rdamedia
001448610 338__ $$aonline resource$$bcr$$2rdacarrier
001448610 504__ $$aIncludes bibliographical references and indexes.
001448610 5050_ $$aMathematical Background; a Review -- A Theory of Computability -- Primitive Recursive Functions -- Loop Programs.-The Ackermann Function -- (Un)Computability via Church's Thesis -- Semi-Recursiveness -- Yet another number-theoretic characterisation of P -- Godel's Incompleteness Theorem via the Halting Problem -- The Recursion Theorem -- A Universal (non-PR) Function for PR -- Enumerations of Recursive and Semi-Recursive Sets -- Creative and Productive Sets Completeness -- Relativised Computability -- POSSIBILITY: Complexity of P Functions -- Complexity of PR Functions -- Turing Machines and NP-Completeness.
001448610 506__ $$aAccess limited to authorized users.
001448610 520__ $$aThis survey of computability theory offers the techniques and tools that computer scientists (as well as mathematicians and philosophers studying the mathematical foundations of computing) need to mathematically analyze computational processes and investigate the theoretical limitations of computing. Beginning with an introduction to the mathematisation of "mechanical process" using URM programs, this textbook explains basic theory such as primitive recursive functions and predicates and sequence-coding, partial recursive functions and predicates, and loop programs. Features: Extensive and mathematically complete coverage of the limitations of logic, including Godels incompleteness theorems (first and second), Rossers version of the first incompleteness theorem, and Tarskis non expressibility of "truth" Inability of computability to detect formal theorems effectively, using Churchs proof of the unsolvability of Hilberts Entscheidungsproblem Arithmetisation-free proof of the pillars of computability: Kleenes s-m-n, universal function and normal form theorems using "Churchs thesis" and a simulation of the URM "register machine" by a simultaneous recursion. These three pivotal results lead to the deeper results of the theory Extensive coverage of the advanced topic of computation with "oracles" including an exposition of the search computability theory of Moschovakis, the first recursion theorem, Turing reducibility and Turing degrees and an application of the Sacks priority method of "preserving agreements", and the arithmetical hierarchy including Posts theorem Cobhams mathematical characterisation of the concept deterministic polynomial time computable function is fully proved A complete proof of Blums speed-up theorem
001448610 588__ $$aOnline resource; title from PDF title page (SpringerLink, viewed August 16, 2022).
001448610 650_0 $$aComputable functions.
001448610 655_0 $$aElectronic books.
001448610 77608 $$iPrint version:$$aTourlakis, George.$$tComputability.$$dCham : Springer International Publishing AG, ©2022$$z9783030832018
001448610 852__ $$bebk
001448610 85640 $$3Springer Nature$$uhttps://univsouthin.idm.oclc.org/login?url=https://link.springer.com/10.1007/978-3-030-83202-5$$zOnline Access$$91397441.1
001448610 909CO $$ooai:library.usi.edu:1448610$$pGLOBAL_SET
001448610 980__ $$aBIB
001448610 980__ $$aEBOOK
001448610 982__ $$aEbook
001448610 983__ $$aOnline
001448610 994__ $$a92$$bISE