Computability Theory

S. Barry Cooper

• Publisher: Chapman and Hall/CRC
• Year: 2017
• ISBN:
  9781351991964
• Edition: 1
• Topic: Matemáticas
• Subtopic: Matemática aplicada

Computability theory originated with the seminal work of Gödel, Church, Turing, Kleene and Post in the 1930s. This theory includes a wide spectrum of topics, such as the theory of reducibilities and their degree structures, computably enumerable sets and their automorphisms, and subrecursive hierarchy classifications. Recent work in computability theory has focused on Turing definability and promises to have far-reaching mathematical, scientific, and philosophical consequences. Written by a leading researcher, Computability Theory provides a concise, comprehensive, and authoritative introduction to contemporary computability theory, techniques, and results. The basic concepts and techniques of computability theory are placed in their historical, philosophical and logical context. This presentation is characterized by an unusual breadth of coverage and the inclusion of advanced topics not to be found elsewhere in the literature at this level.The book includes both the standard material for a first course in computability and more advanced looks at degree structures, forcing, priority methods, and determinacy. The final chapter explores a variety of computability applications to mathematics and science.Computability Theory is an invaluable text, reference, and guide to the direction of current research in the field. Nowhere else will you find the techniques and results of this beautiful and basic subject brought alive in such an approachable and lively way.

Part I

Computability and Unsolvable Problems

Chapter 1

Hilbert and the Origins of Computability Theory

It is only in the last century that computability became both a driving force in our daily lives and a concept one could talk about with any sort of precision. Computability as a theory is a specifically twentieth-century development. And so of course is the computer, and this is no coincidence. But this contemporary awareness and understanding of the algorithmic content of everyday life has its roots in a rich history.

1.1 Algorithms and Algorithmic Content

We can see now that the world changed in 1936, in a way quite unrelated to the newspaper headlines of that year concerned with such things as the civil war in Spain, economic recession, and the Berlin Olympics. The end of that year saw the publication of a thirty-six page paper by a young mathematician, Alan Turing, claiming to solve a long-standing problem of the distinguished German mathematician David Hilbert. A by-product of that solution was the first machine-based model of what it means for a number-theoretic function to be computable, and the description of what we now call a Universal Turing Machine. At a practical level, as Martin Davis describes in his 2001 book Engines of Logic: Mathematicians and the Origin of the Computer, the logic underlying such work became closely connected with the later development of real-life computers. The stored-program computer on one’s desk is a descendant of that first universal machine. What is less often remembered is Turing’s theoretical contribution to the understanding of the limitations on what computers can do. There are quite easily described arithmetical functions which are not computable by any computer, however powerful. And even the advent of quantum computers will not change this.

Before computers, computer programs used to be called algorithms. Algorithms were just a finite set of rules, expressed in everyday language, for performing some general task. What is special about an algorithm is that its rules can be applied in potentially unlimited instances of a particular situation. We talk about the algorithmic content of Nature when we recognise patterns in natural phenomena which appear to follow general rules. Ideally algorithms and algorithmic content need to be captured precisely in the language of mathematics, but this is not always easy. There are areas (such as sociology or the biological sciences) where we must often resort to language dealing with concepts not easily reducible to numbers and sets. One of the main tasks of science, at least since the time of...