Though we did not know it at the time, this book’s genesis began with the arrival of Cris Calude in New Zealand. Cris has always had an intense interest in algorithmic information theory. The event that led to much of the recent research presented here was the articulation by Cris of a seemingly innocuous question. This question...

This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations.  Subsequent chapters move from the qualitative aspects of...

It may sound less surprising that in a field with such a revolutionary methodological impact on all sciences and...

Logic is a branch of philosophy, mathematics and computer science. It studies the required methods to determine whether a statement is true, such as reasoning and computation.

Proofs and Algorithms: Introduction to Logic and Computability is an introduction to the fundamental concepts of contemporary logic - those of a...

The Formal Semantics of Programming Languages provides the basic mathematical techniques necessary for those who are beginning a study of the semantics and logics of programming languages. These techniques will allow students to invent, formalize, and justify rules with which to reason about a variety of programming languages. Although...

This book is an introduction to theoretical computer science emphasizing two interrelated areas: the theory of computability {how to tell whether problems are algorithmically solvable) and the theory of formal languages (how to design and use special languages, as for algorithms). Automata {idealized computer devices) are used as precise...

One of the most striking features of mathematics is the fact that we are much more certain about the mathematical knowledge we have than about what mathematical knowledge is knowledge of. Are numbers, sets, functions and groups physical entities of some kind? Are they objectively existing objects in some non-physical, mathematical realm? Are...

In an extraordinary and ultimately tragic life that unfolded like a novel, Turing helped break the German Enigma code to turn the tide of World War II, later speculated on...