computability
≈ 3 min read
Names in other languages
- TürkçeHesaplanabilirlik
- DeutschBerechenbarkeitTuring-Berechenbarkeit, Rekursivität, effektive Berechenbarkeit, berechenbare Funktion, berechenbar
- NederlandsberekenbaarheidEntscheidungsproblem, Beslisbaarheid
- Portuguêscomputabilidade
- Portuguêscomputabilidade
- skvypočítateľnosť
- Españolcalculabilidadteoría de la calculabilidad, teoría de la recursión, función calculable, teoria de la calculabilidad, teoria de la recursion, funcion calculable
- gswBerächebarkeit
- Українськаобчислюваність
- Englishcomputability
- Françaiscalculabilitécalculable, incalculable, calculabilite, fonctions calculables
- Italianocomputabilità
- eokomputebleco
- فارسیمحاسبهپذیری
- htKalkilablite
- ioKomputebleso
- Русскийвычислимостьисчисляемость
- bgизчислимост
- العربيةالحاسوبية
- עבריתחישוביותתורת החישוביות
- yue可運算性
- 中文可计算性
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation.
Computability is the ability to solve a problem by an effective procedure. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.
Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation. A function problem consists of a function f from a set U to a set V. An instance of the problem is to compute, given an element u in U, the corresponding element f(u) in V.
For example, U and V may be the set of all finite binary strings, and f may take a string and return the string obtained by reversing the digits of the input (so f(0101) = 1010). Other types of problems include search problems and optimization problems. One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation. 1 = \sum_{n=1}^{\infty} \frac{1}{2^n} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots time unit (and 1 energy unit...) to run.
This infinite series converges to 1, which means that this Zeno machine can execute a countably infinite number of steps in 1 time unit (using 1 energy unit...). This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question. By extension, any convergent infinite [must be provably infinite] series would work. Assuming that the infinite series converges to a value n, the Zeno machine would complete a countably infinite execution in n time units.
See also
Automata theory Abstract machine List of undecidable problems Computational complexity theory Computability logic
Text derived from https://en.wikipedia.org/w/index.php?oldid=1365546104 under CC BY-SA 4.0; modifications have been made.