計算可能性理論（第２版）<br>Computability Theory (Chapman Hall/crc Mathematics) （2 Revised）

  • ポイントキャンペーン

計算可能性理論（第２版）
Computability Theory (Chapman Hall/crc Mathematics) （2 Revised）

  • ただいまウェブストアではご注文を受け付けておりません。 ⇒古書を探す
  • 製本 Hardcover:ハードカバー版／ページ数 506 p.
  • 言語 ENG
  • 商品コード 9781439838433
  • DDC分類 511

基本説明

Designed for advanced undergraduate or beginning graduate students, this second edition includes new material on hyperarithmetical and Borel sets as well as more material on computability of structures, Pi-0-1 classes, and computability in science.

Full Description


Designed for advanced undergraduate or beginning graduate students, this book provides a complete introduction to computability theory. This second edition includes new material on hyperarithmetical and Borel sets as well as more material on computability of structures, Pi-0-1 classes, and computability in science. It features an expanded treatment of complexity of computations and updated future directions in computability. In addition, the section on randomness is now a separate chapter. The author also discusses advanced topics in greater depth, including Post's problem, forcing and category, applications of determinacy, and the computability of theories.

Contents

COMPUTABILITY AND UNSOLVABLE PROBLEMS Hilbert and the Origins of Computability Theory Models of Computability and the Church-Turing Thesis Language, Proof and Computable Functions Coding, Self-Reference and the Universal Turing Machine Enumerability and Computability The Search for Natural Examples of Incomputable Sets Comparing Computability and the Ubiquity of Creative Sets Godel's Incompleteness Theorem Decidable and Undecidable Theories INCOMPUTABILITY AND INFORMATION CONTENT Computing with Oracles Nondeterminism, Enumerations and Polynomial Bounds Complexity of Computations MORE ADVANCED TOPICS Post's Problem: Immunity and Priority Forcing and Category The Computability of Theories Randomness Computability and Structure Computability and Incomputability in Science