Computability theory

Computability theory is a interesting area that connects mathematical logic, computer science, and the theory of computation. It started in the 1930s when scientists began to study what kinds of problems can be solved by computers or calculations. This field helps us learn the limits of what machines—and even people—can calculate.

One big question in computability theory is: what does it mean for a function, which uses natural numbers like 1, 2, 3, and so on, to be computable? In simple terms, can a computer or a person follow steps to find an answer for any input? This theory also studies functions that cannot be computed and tries to group them based on how “hard” they are to calculate.

People who study computability theory from a math point of view often look at how one problem can help solve another and how these problems are linked. In computer science, the focus is more on formal ways to describe calculations, different levels of calculation difficulty, and the languages computers use to understand instructions. All of this helps us understand what can and cannot be done well through calculation, a part of what is sometimes called recursive mathematics.

Introduction

Computability theory started 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 explains what it means to calculate something step by step. Later, their ideas led to 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 found 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 idea of computability was introduced by Turing in 1936. A group of numbers is called a computable set if a special machine, called a Turing machine, 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 ways to think about computation, but they all work like 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.

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 researcher named Robert I. Soare thinks it should be called "computability theory" instead. He believes the word "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 words. 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 like 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.