Computability theory : concepts and applications
著者
書誌事項
Computability theory : concepts and applications
（Ellis Horwood series in computers and their applications）
Ellis Horwood, 1991
- : pbk
大学図書館所蔵 全4件
注記
Includes bibliographical references (p. 143) and index
内容説明・目次
内容説明
Computability theory is the branch of computer science concerned with identifying which computational problems cannot be solved by computer programs. Paul Dunne provides a basic introduction to the subject of computability that is primarily aimed at students of computer science. The text motivates the concept of models of computation as abstract representations of computer behaviour and illustrates how proofs of non-computability may be constructed with respect to these. The final chapters develop a much simplified proof of Godel's work on provability. The primary concern of the text is to motivate the important concerns of computability theory as a discipline within computer science rather than as an abstract mathematical subject. In contrast with many existing texts, the book is written in an easy-to-read style, providing a welcomingly straightforward review of computability theory.
目次
- Turing machines
- turing machines as recognisers
- universality
- undecidability
- alternative models
- post's correspondence problem
- recursive function theory
- formal models of arithmetic
- Godel's incompleteness theorem
- computer science and computability theory.
「Nielsen BookData」 より