Additional References
It is not required (and should not be necessary) to use material that is not freely provided on the course web site, in order do well in CPSC 513 or CPSC 601.08. Furthermore, material that you find online can be highly unreliable: Sometimes technical terms, used in this course, are used in inconsistent (and, very different) ways. The internet includes many misleading — and, sometimes, downright false — claims about things that are being studied here.
Students in CPSC 601.08 are being asked to complete a project on a topic that extends, or applies, the course material — so that these students probably do need additional material. Several of the references that are listed, below, include at least a little bit of material that might be useful to begin work on a CPSC—601.08 project.
Several of these references are freely available to University of Calgary, as ebooks, through the University of Calgary. An “ebook” link is provided for the text, below, when this is the case.
In Case You Need To Review
- S. S. Epp, Discrete Mathematics with Applications
Fifth Edition, Brooks Cole, 2019
- K. H. Rosen, Discrete Mathematics and Its
Applications
Eighth Edition, McGraw Hill, 2018
One of these is frequently used as a textbook or recommended reference for MATH 271, while the other is frequently used as a textbook or recommended reference for CPSC 251. They are both readable references for the material, in discrete mathematics (as well as logic and proofs), that are covered in prerequisite courses and that will be assumed as background for CPSC 513.
- D. C. Kozen, Automata and Computability
Corrected Edition, Springer, 2007: [ Ebook ]
This book presents material about automata and computability theory that is included in the prerequisite course, CPSC 351 — but it is written at a somewhat higher level, and includes a considerable amount of additional material. Some of this material might be the basis for the beginning of a CPSC 601.08 project. This is freely available to University of Calgary students as an ebook.
Main Reference for Course Material
- M. D. Davis, R. Sigal, and E. J. Weyuker,
Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science
Second Edition, Morgan Kaufmann, 1994: [ Ebook ]
Parts 1 and 2 of this text were consulted heavily, when preparing an earlier version of this course, and quite a bit of the current version of the course is still based on this material.
A simple programming language is introduced in this text (and in this course) and used to define “computable functions,” with Turing machines introduced later. While this adds extra material that computer science students must learn, at the beginning of the course, it simplifies proofs of a variety of claims in the course, later on.
This is also freely available to University of Calgary students as an ebook.
Alternative References for Course Material
- B. Robič,
The Foundations of Computability Theory
Second Edition, Springer, 2020: [ Ebook ]
A readable text that places computability theory in a historical perspective. Since Turing machines are used as the model of computation, nontrivial results about computable function are described with proof sketches instead of detailed proofs — but these can certainly help to understand how various results can be proved. This also includes a useful guide for further reading as its final chapter. Once again, this is freely available to University of Calgary students as an ebook.
- G. Tourlakis,
Computability
Springer, 2022: [ Ebook ]
Since this uses a programming model (with “URM programs”) it can present proofs at a level of detail similar to what is possible in the main course reference. This goes somewhat beyond the course material, presenting early results in computational complexity theory (which are often left out in textbooks on that subject). This is also freely available to University of Calgary students as an ebook.
