Computable set

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. A set which is not computable is called noncomputable or undecidable. A more general class of sets than the computable ones consists of the computably enumerable (c.e.) sets, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number is in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set. A subset of the natural numbers is called computable if there exists a total computable function such that if and if . In other words, the set is computable if and only if the indicator function is computable. Examples: Every finite or cofinite subset of the natural numbers is computable. This includes these special cases: The empty set is computable. The entire set of natural numbers is computable. Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable. The subset of prime numbers is computable. A recursive language is a computable subset of a formal language. The set of Gödel numbers of arithmetic proofs described in Kurt Gödel's paper "On formally undecidable propositions of Principia Mathematica and related systems I" is computable; see Gödel's incompleteness theorems. Non-examples: List of undecidable problems The set of Turing machines that halt is not computable. The isomorphism class of two finite simplicial complexes is not computable. The set of busy beaver champions is not computable. Hilbert's tenth problem is not computable. If A is a computable set then the complement of A is a computable set. If A and B are computable sets then A ∩ B, A ∪ B and the image of A × B under the Cantor pairing function are computable sets.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (24)

Related courses (6)

Related lectures (33)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

Computable set

Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine.

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.

Convergence Analysis: Explicit RK Scheme MATH-351: Advanced numerical analysis

Explores the convergence analysis of the Explicit Runge-Kutta scheme for accurate numerical solutions.

Recursive Algorithms: Induction & Sorting CS-101: Advanced information, computation, communication I

Explores induction, recursion, and sorting algorithms, including merge sort and the proof of correctness for recursive algorithms.

Recursive Algorithms: Induction & Sorting CS-101: Advanced information, computation, communication I

Covers induction, recursion, sorting algorithms, and the merge sort complexity in computer science.