Computability: An Introduction to Recursive Function Theory

Front Cover
Cambridge University Press, Jun 19, 1980 - Computers - 251 pages
2 Reviews
What can computers do in principle? What are their inherent theoretical limitations? These are questions to which computer scientists must address themselves. The theoretical framework which enables such questions to be answered has been developed over the last fifty years from the idea of a computable function: intuitively a function whose values can be calculated in an effective or automatic way. This book is an introduction to computability theory (or recursion theory as it is traditionally known to mathematicians). Dr Cutland begins with a mathematical characterisation of computable functions using a simple idealised computer (a register machine); after some comparison with other characterisations, he develops the mathematical theory, including a full discussion of non-computability and undecidability, and the theory of recursive and recursively enumerable sets. The later chapters provide an introduction to more advanced topics such as Gildel's incompleteness theorem, degrees of unsolvability, the Recursion theorems and the theory of complexity of computation. Computability is thus a branch of mathematics which is of relevance also to computer scientists and philosophers. Mathematics students with no prior knowledge of the subject and computer science students who wish to supplement their practical expertise with some theoretical background will find this book of use and interest.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

I
1
II
2
III
4
V
5
VI
7
VIII
9
IX
16
X
22
XXXIX
112
XL
121
XLII
123
XLIII
133
XLIV
140
XLV
143
XLVII
146
XLVIII
149

XI
23
XII
25
XIII
29
XIV
32
XV
42
XVI
48
XVIII
49
XIX
51
XX
52
XXI
57
XXII
65
XXIII
67
XXIV
72
XXVI
76
XXVII
79
XXVIII
81
XXIX
85
XXXI
90
XXXII
93
XXXIII
100
XXXIV
101
XXXV
106
XXXVI
107
XXXVII
108
XXXVIII
109
XLIX
155
L
157
LI
158
LII
161
LIII
165
LIV
167
LV
174
LVI
182
LVIII
189
LIX
192
LX
196
LXI
200
LXII
207
LXIII
210
LXIV
212
LXV
213
LXVI
218
LXVII
223
LXVIII
225
LXIX
236
LXX
239
LXXI
241
LXXII
246
Copyright

Common terms and phrases

References to this book

All Book Search results »

About the author (1980)

Cutland, Department of Pure Mathematics, University of Hull.

Bibliographic information