Computability theory

Computability theory is a fascinating area that sits at the meeting point of mathematical logic, computer science, and the theory of computation. It began in the 1930s when scientists started to explore what kinds of problems can actually be solved by computers or through calculation. This field helps us understand the limits of what machines—and even people—can compute.

One of the big questions in computability theory is: what does it mean for a function, which works with natural numbers like 1, 2, 3, and so on, to be computable? In other words, can a computer or a person follow a set of steps to find an answer for any input? This theory also looks at functions that cannot be computed and tries to sort them into levels based on how “hard” they are to compute.

People who study computability theory from a mathematical angle often look at how one problem can help solve another and how these problems are connected in a structure. In computer science, the focus is more on formal ways to describe computations, different levels of computation difficulty, and the languages that computers use to understand instructions. All of this helps us understand what can and cannot be done effectively through computation, a part of what is sometimes called recursive mathematics.

Introduction

Computability theory began in the 1930s with the work of Kurt Gödel, Alonzo Church, Rózsa Péter, Alan Turing, Stephen Kleene, and Emil Post.

These researchers showed that Turing computability correctly describes what it means to calculate something step by step. Later, these ideas led to what is now called the Church–Turing thesis, which says that any problem that can be solved by following steps can also be solved by a computer.

They also discovered that some math problems cannot be solved by any step-by-step method. For example, they proved that there is no way to always tell if a math statement is true or false. Many other important math problems were later shown to have no solution using steps either.

Turing computability

The main idea of computability was introduced by Turing in 1936. A group of numbers is called a computable set if there is a special machine, called a Turing machine, that can tell us whether a number is in that group or not. A rule or method is computable if the same kind of machine can follow the rule and give us an answer for any input.

There are many different ways to think about computation, but they all work the same way as Turing machines. However, not every group of numbers can be checked this way. One famous example is the halting problem, where it is impossible to know for sure if a program will stop running or keep going forever.

Areas of research

Computability theory studies different ways to understand what can be computed. It began with simple ideas about computable functions and has grown to include many related topics. These areas all connect to each other, and researchers often work across several of them.

Relative computability and the Turing degrees

Computability theory has focused on relative computability. This idea, introduced by Turing in 1939, uses oracle Turing machines. These are imaginary devices that can ask questions to an oracle—a special set of numbers—and get immediate answers. With a noncomputable oracle, these machines can solve problems that regular computers cannot.

A set of numbers is Turing reducible to another set if an oracle machine can determine membership using the second set as an oracle. If two sets are Turing reducible to each other, they share the same Turing degree, which measures how hard they are to compute.

Other reducibilities

Researchers also study other types of reducibility besides Turing reducibility. Some of these, like truth-table reducibility, allow a machine to ask several questions at once to an oracle. Others, like arithmetical reducibility, connect to how mathematical statements can be defined.

Rice's theorem and the arithmetical hierarchy

Rice's theorem shows that certain problems about programs always have solutions that are either very easy or very hard to solve. These problems can be organized using the arithmetical hierarchy, which classifies mathematical statements by their complexity.

Reverse mathematics

Reverse mathematics explores which basic mathematical rules are needed to prove different theorems. This work helps understand the foundations of mathematics.

Numberings

Numberings are ways to list functions by giving each one a number. Researchers study which numbering systems allow all functions to be translated into each other.

The priority method

The priority method is a technique used to build sets with specific properties. It involves setting goals and deciding how to meet them when conflicts arise.

The lattice of computably enumerable sets

Researchers also study the structure of sets that can be listed by computers, exploring their relationships and properties.

Kolmogorov complexity

Kolmogorov complexity measures how hard it is to describe a piece of data. It connects to ideas about randomness and has many applications in understanding computation.

Frequency computation

This area looks at sets where most answers to certain questions are correct, even if not all are. It helps understand different ways computers can approximate solutions.

Inductive inference

Inductive inference studies how computers can learn patterns from data. It builds on models of learning developed in the 1960s and has many applications in artificial intelligence.

Generalizations of Turing computability

Computability theory also explores ideas beyond Turing machines, such as reducibilities that involve more complex mathematical statements. These studies connect to set theory and the study of infinite processes.

Continuous computability theory

Finally, computability theory also looks at computation in systems that change continuously, like those modeled by differential equations. This includes studying computation in analog computers and neural networks.

Relationships between definability, proof and computability

There are important links between how we describe sets of numbers and what we can calculate about them. For example, Post's theorem explains one of these links clearly. Kurt Gödel also showed that what we can prove in math is connected to what we can calculate.

Computability theory connects to a special kind of math called second-order arithmetic. This helps us understand which math ideas can be described simply. A field called reverse mathematics uses these ideas to study famous math results.

Name

The study of what can be calculated is called "recursion theory." A well-known researcher, Robert I. Soare, thinks it should be called "computability theory" instead. He believes the term "computable" is easier to understand than "recursive." Many researchers now use words like partial computable function and computably enumerable (c.e.) set instead of older terms. However, not everyone agrees with this change. Some say both names do not clearly show that most things studied in this field cannot actually be computed.

In 1967, Rogers suggested that a main idea in computability theory is that its findings should stay the same even if numbers are renamed in a certain way. This is similar to how turning a shape does not change its basic properties. According to Rogers, the important sets in this theory are those that cannot be computed, grouped by special kinds of renaming.

Professional organizations

The main group for computability theory is the Association for Symbolic Logic. They have many research meetings each year. Another group, called Computability in Europe (CiE), also holds yearly meetings for people studying many different areas of science together.