國立虎尾科技大學 |

Computability

Record Type:	Language materials, printed : Monograph/item
Title/Author:	Computability/ by George Tourlakis.
Author:	Tourlakis, George.
Description:	XXVII, 637 p. 12 illus., 10 illus. in color.online resource. :
Contained By:	Springer Nature eBook
Subject:	Computer science. -
Online resource:	https://doi.org/10.1007/978-3-030-83202-5
ISBN:	9783030832025

Computability
Tourlakis, George.

Computability[electronic resource] /by George Tourlakis. - 1st ed. 2022. - XXVII, 637 p. 12 illus., 10 illus. in color.online resource.

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 Gö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:

573171
Computer science.

LC Class. No.: QA75.5-76.95

Dewey Class. No.: 004.0151

Computability
LDR:03734nam a22003975i 4500 001 1089283
003 DE-He213
005 20220802193423.0
007 cr nn 008mamaa
008 221228s2022 sz | s |||| 0|eng d
020 $a 9783030832025 $9 978-3-030-83202-5
024 7 $a 10.1007/978-3-030-83202-5 $2 doi
035 $a 978-3-030-83202-5
050 4 $a QA75.5-76.95
072 7 $a UYA $2 bicssc
072 7 $a COM014000 $2 bisacsh
072 7 $a UYA $2 thema
082 0 4 $a 004.0151 $2 23
100 1 $a Tourlakis, George. $4 aut $4 http://id.loc.gov/vocabulary/relators/aut $3 685608
245 1 0 $a Computability $h [electronic resource] / $c by George Tourlakis.
250 $a 1st ed. 2022.
264 1 $a Cham : $b Springer International Publishing : $b Imprint: Springer, $c 2022.
300 $a XXVII, 637 p. 12 illus., 10 illus. in color. $b online resource.
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
347 $a text file $b PDF $2 rda
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 Gö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 Computer science. $3 573171
650 0 $a Computable functions. $3 677058
650 0 $a Recursion theory. $3 575916
650 0 $a Computational complexity. $3 527777
650 0 $a Technology—Philosophy. $3 1387770
650 1 4 $a Theory of Computation. $3 669322
650 2 4 $a Computability and Recursion Theory. $3 1396185
650 2 4 $a Computational Complexity. $3 1366362
650 2 4 $a Models of Computation. $3 1365746
650 2 4 $a Philosophy of Technology. $3 671635
710 2 $a SpringerLink (Online service) $3 593884
773 0 $t Springer Nature eBook
776 0 8 $i Printed edition: $z 9783030832018
776 0 8 $i Printed edition: $z 9783030832032
776 0 8 $i Printed edition: $z 9783030832049
856 4 0 $u https://doi.org/10.1007/978-3-030-83202-5
912 $a ZDB-2-SCS
912 $a ZDB-2-SXCS
950 $a Computer Science (SpringerNature-11645)
950 $a Computer Science (R0) (SpringerNature-43710)