Computability

Computability is the ability to solve a problem using a clear, step-by-step method. It is an important idea in the field of computability theory, which is part of mathematical logic and the theory of computation in computer science. Whether a problem is computable depends on whether there is an algorithm that can solve it.

People often study models like Turing-computable problems, μ-recursive functions, and the lambda calculus. These models all have the same level of power when it comes to solving problems. Some areas look at weaker forms of computability, like those studied in automata theory, while others explore ideas even stronger than what a Turing machine can do, such as those in hypercomputation. Understanding computability helps us know what problems can truly be solved by computers and how they can be solved.

Problems

A central idea in computability is that of a computational problem, which is a task we can try to solve using a computer or a clear set of steps.

There are two main types of problems. A decision problem asks us to decide whether something is true or false. For example, we might want to know if a number is prime. A function problem asks us to compute a result from an input. For example, we might take a string of numbers and reverse their order. Other types of problems include search problems and optimization problems. Computability theory studies which problems can be solved using different computing methods.

Formal models of computation

Main article: Model of computation

A model of computation is a way to describe how a computer or any computing system works. It helps us understand what problems can be solved and how they can be solved step by step. One important model is the Turing machine, which uses a long tape to read, write, and move around symbols, showing what any computer can do given enough time and space.

Other models include lambda calculus, which uses special expressions and rules to change them, and combinatory logic, which uses different rules but can do similar things. There are also simpler models like finite automata, which have a set number of states and change based on inputs, and pushdown automata, which have a stack to help remember things. These models help scientists study what can and cannot be computed.

Power of automata

With computational models, we can explore their limits and understand what types of problems they can solve.

Power of finite-state machines

A regular language is one that can be recognized by a finite-state machine. However, there are languages that cannot be recognized this way. For example, the language of all strings with an equal number of 'a's and 'b's cannot be recognized by a finite-state machine because it would need an infinite number of states to track the balance between the two letters.

Power of pushdown automata

A Context-free language can be recognized by a pushdown automaton, which is more powerful than a finite-state machine. This model can handle languages like the one with equal numbers of 'a's and 'b's. However, there are still some languages, such as those involving prime numbers, that even pushdown automata cannot recognize.

Power of Turing machines

Turing machines are the most powerful computational models. They can recognize any context-free language and even more complex languages. Turing machines can simulate any other computational model, showing their ultimate flexibility in solving problems.

Concurrency-based models

Several computational models based on concurrency have been created, such as the parallel random-access machine and the Petri net. Even though these models allow many tasks to happen at the same time, they can only perform calculations that a Turing machine could also do. This means that, despite being different, they do not go beyond the limits of what we consider computable.

Stronger models of computation

The Church–Turing thesis suggests that no computing model can do more than a Turing machine. However, computer scientists have imagined special machines called hypercomputers that go beyond normal computing rules.

Some ideas include machines that can do infinite steps in a very short time, called Zeno machines, and machines that can ask special questions called "oracles" to solve problems that normal machines cannot. Even these powerful machines have their own limits and cannot solve every possible problem.