co-recursively enumerable

co-recursively enumerable
Describing a set for which there exists a deterministic algorithm that will list all items not in that set.

Any recursively enumerable set which is also co-recursively enumerable is a decidable set.


Wikipedia foundation.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Recursively enumerable set — In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing recognizable if: There is an algorithm such that the set of… …   Wikipedia

  • Recursively enumerable language — In mathematics, logic and computer science, a recursively enumerable language is a type of formal language which is also called partially decidable or Turing acceptable. It is known as a type 0 language in the Chomsky hierarchy of formal… …   Wikipedia

  • recursively enumerable — adjective Of a set, such that there exists a deterministic algorithm which will list all the items in the set and no others …   Wiktionary

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Turing degree — Post s problem redirects here. For the other Post s problem , see Post s correspondence problem. In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic …   Wikipedia

  • Creative and productive sets — In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as Soare (1987) and Rogers… …   Wikipedia

  • Computability — You might be looking for Computable function, Computability theory, Computation, or Theory of computation. Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within… …   Wikipedia

  • Alpha recursion theory — In recursion theory, the mathematical theory of computability, alpha recursion (often written α recursion) is a generalisation of recursion theory to subsets of admissible ordinals alpha. An admissible ordinal is closed under Sigma 1(L alpha)… …   Wikipedia

  • mathematics, foundations of — Scientific inquiry into the nature of mathematical theories and the scope of mathematical methods. It began with Euclid s Elements as an inquiry into the logical and philosophical basis of mathematics in essence, whether the axioms of any system… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”