東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁 到查詢結果 [ subject:"Computational Complexity." ]

切換: 標籤 | MARC模式 | ISBD

Computability

Tourlakis, George J.

FindBook

Google Book

Amazon

博客來

Computability

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Computability/ by George Tourlakis.
作者:	Tourlakis, George J.
出版者:	Cham :Springer International Publishing : : 2022.,
面頁冊數:	xxvii, 637 p. :ill., digital ;24 cm.
內容註:	Mathematical 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.
Contained By:	Springer Nature eBook
標題:	Computable functions. -
電子資源:	https://doi.org/10.1007/978-3-030-83202-5
ISBN:	9783030832025

Computability
Tourlakis, George J.

Computability[electronic resource] /by George Tourlakis. - Cham :Springer International Publishing :2022. - xxvii, 637 p. :ill., digital ;24 cm.

Mathematical 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.

This 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 Gödel's incompleteness theorems (first and second), Rosser's version of the first incompleteness theorem, and Tarski's non expressibility of "truth" Inability of computability to detect formal theorems effectively, using Church's proof of the unsolvability of Hilbert's Entscheidungsproblem Arithmetisation-free proof of the pillars of computability: Kleene's s-m-n, universal function and normal form theorems - using "Church's 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 Post's theorem Cobham's mathematical characterisation of the concept deterministic polynomial time computable function is fully proved A complete proof of Blum's speed-up theorem.

ISBN: 9783030832025

Standard No.: 10.1007/978-3-030-83202-5doiSubjects--Topical Terms:

559829
Computable functions.

LC Class. No.: QA9.59 / .T68 2022

Dewey Class. No.: 511.352

Computability
LDR:03317nmm a2200325 a 4500 001 2302475
003 DE-He213
005 20220802193423.0
006 m d
007 cr nn 008maaau
008 230409s2022 sz s 0 eng d
020 $a 9783030832025 $q (electronic bk.)
020 $a 9783030832018 $q (paper)
024 7 $a 10.1007/978-3-030-83202-5 $2 doi
035 $a 978-3-030-83202-5
040 $a GP $c GP
041 0 $a eng
050 4 $a QA9.59 $b .T68 2022
072 7 $a UYA $2 bicssc
072 7 $a COM014000 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 511.352 $2 23
090 $a QA9.59 $b .T727 2022
100 1 $a Tourlakis, George J. $3 864303
245 1 0 $a Computability $h [electronic resource] / $c by George Tourlakis.
260 $a Cham : $b Springer International Publishing : $b Imprint: Springer, $c 2022.
300 $a xxvii, 637 p. : $b ill., digital ; $c 24 cm.
505 0 $a Mathematical 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.
520 $a This 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 Gödel's incompleteness theorems (first and second), Rosser's version of the first incompleteness theorem, and Tarski's non expressibility of "truth" Inability of computability to detect formal theorems effectively, using Church's proof of the unsolvability of Hilbert's Entscheidungsproblem Arithmetisation-free proof of the pillars of computability: Kleene's s-m-n, universal function and normal form theorems - using "Church's 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 Post's theorem Cobham's mathematical characterisation of the concept deterministic polynomial time computable function is fully proved A complete proof of Blum's speed-up theorem.
650 0 $a Computable functions. $3 559829
650 1 4 $a Theory of Computation. $3 892514
650 2 4 $a Computability and Recursion Theory. $3 3602807
650 2 4 $a Computational Complexity. $3 3538876
650 2 4 $a Models of Computation. $3 3592010
650 2 4 $a Philosophy of Technology. $3 897015
710 2 $a SpringerLink (Online service) $3 836513
773 0 $t Springer Nature eBook
856 4 0 $u https://doi.org/10.1007/978-3-030-83202-5
950 $a Computer Science (SpringerNature-11645)