Computability, complexity, logic

>> Google Books

所蔵情報QRコード

Computability, complexity, logic / E. Börger ; [translated into the English language and prepared for offset printing by J.C. Harvey]

資料種別:: 図書
出版情報:: Amsterdam ; New York : North-Holland
New York : Distributors for U.S.A. and Canada, Elsevier Science Publishing Company, Inc., 1989
形態:: xx, 592 p. ; 23 cm
シリーズ名:: Studies in logic and the foundations of mathematics ; v. 128 <BA00099329>
著者名:: Börger, Egon, 1946- <DA01377208>
ISBN:: 9780444874061 [0444874062]
書誌ID:: BA07194157

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

その他の標題:

Berechenbarkeit, Komplexität, Logik

注記:

Originally published: F. Vieweg & Sohn Verlagsgesellschaft GmbH., 1985
Includes bibliography (p. 529-573) and index
Copyright Elsevier Science Publishers B.V., 1989

主題:

Computable functions; Computational complexity; Logic, Symbolic and mathematical

言語:

英語

目次情報:

Elementary Theory of Computation

The Mathematical Concept of Algorithm

Church's Thesis

Universal Programs and the Recursion Theorem

Complexity of Algorithmic Unsolvability

Recursively Unsolvable Problems

The Arithmetical Hierarchy and Degrees of Unsolvability

Abstract Complexity of Computation

Recursiveness and Complexity

Complexity Classes of Recursive Functions

Complexity Classes of Primitive Recursive Functions

Polynomially- and Exponentially-Bounded Complexity Classes

Finite Automata

Context-Free Languages

Elementary Predicate Logic

Logical Analysis of the Truth Concept

Syntax and Semantics

Completeness Theorem

Consequences of the Completeness Theorem

Logical Analysis of the Concept of Proof

Gentzen's Calculus LK

Cut Elimination for LK

Consequences of the Cut Elimination Theorem

Complexity of Logical Decision Problems

Undecidability and Reduction Classes

Incompleteness of Arithmetic

Recursive Lower Complexity Bounds

Bibliography

Index

Elementary Theory of Computation

The Mathematical Concept of Algorithm

Church's Thesis

Universal Programs and the Recursion Theorem

Complexity of Algorithmic Unsolvability

Recursively Unsolvable Problems

続きを見る

東工大ブックレビュー

類似資料:

1 図書 CSL '88 : 2nd Workshop on Computer Science Logic, Duisburg, FRG, October 3-7, 1988 : proceedings (: gw ; : us) Workshop on Computer Science Logic, Börger, Egon, 1946-, Richter, Michael M., 1938-, Kleine Büning, Hans, 1948- Springer-Verlag	7 図書 Complexity, logic, and recursion theory Sorbi, Andrea, 1956- Marcel Dekker
2 図書 Computability and logic (: U.K. - : U.S., pbk) Cohen, Daniel E. E. Horwood, Halsted Press [distributor]	8 図書 Computation and automata Salomaa, Arto, 1934- Cambridge University Press
3 電子ブック Computability and logic / ((ebook)) Boolos, George, Burgess, John P., Jeffrey, Richard C.	9 図書 Bounded arithmetic, propositional logic, and complexity theory Krajíček, Jan Cambridge University Press
4 図書 Computability : computable functions, logic, and the foundations of mathematics Epstein, Richard L., 1947-, Carnielli, Walter A. (Walter Alexandre) Wadsworth & Brooks/Cole Advanced Books & Software	10 図書 Computer science logic : 4th workshop, CSL '90, Heidelberg, Germany, October 1-5, 1990 : proceedings (: gw ; : us) Workshop on Computer Science Logic, Börger, Egon, 1946- Springer-Verlag
5 図書 Descriptive complexity Immerman, Neil, 1953- Springer	11 図書 Computer science logic : 5th Workshop, CSL '91, Berne, Switzerland, October, 7-11, 1991 : proceedings (: gw ; : us) Workshop on Computer Science Logic, Börger, Egon, 1946- Springer-Verlag
6 電子ブック Logic and Machines: Decision Problems and Complexity Börger SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg	12 図書 Computer science logic : 6th workshop, CSL '92, San Miniato, Italy, September 28-October 2, 1992 : selected papers (: gw ; : us) Workshop on Computer Science Logic, Börger, Egon, 1946- Springer-Verlag