Computability and complexity theory should be focal points for both practitioners and theorists. Regrettably, the field is often considered challenging to navigate. Neil Jones seeks to bridge the gap between computability and complexity theory and other realms of computer science, particularly programming. Departing from the traditional Turing machine and Gödel number-centric approaches, Jones employs concepts commonly found in programming languages. This approach aims to make computability and complexity more accessible to computer scientists and more relevant to practical programming challenges.
Jones contends that computability and complexity theory, along with programming languages and semantics, have much to offer each other. The former possesses a breadth, depth, and generality rarely seen in programming languages. Conversely, the programming language community excels in algorithm design, presentation, and implementation. Additionally, programming languages occasionally offer computational models that are more realistic in certain crucial aspects than traditional models.
Noteworthy results in the book include a proof emphasizing the significance of constant time factors for its programming-oriented computation model. This stands in contrast to Turing machines, which exhibit a counterintuitive “constant speedup” property. The book introduces simple characterizations in programming terms for key complexity classes such as PTIME and LOGSPACE. It also presents a novel approach to complete problems for NLOGSPACE, PTIME, NPTIME, and PSPACE, uniformly based on Boolean programs.
Download
See also
- Software Exorcism: A Handbook for Debugging and Optimizing Legacy Code by Bill Blunden (2003)
- Hormones and the Endocrine System: Textbook of Endocrinology by Bernhard Kleine (2016)
- Genetics: A Conceptual Approach 6e by Benjamin A. Pierce (2017)
- A Functional Approach to Java by Ben Weidig (2022)
- Calculus of variations and optimal control by Amol Sasan (2005)