Effectively separable

Effectively separable

In computability theory, two sets of natural numbers are effectively separable if it is possible to separate the sets with a computable set, and effectively inseparable otherwise.

Formal definition

Let "A" and "B" be disjoint sets of natural numbers. These sets are effectively separable if there is a computable set "C" of natural numbers such that A subseteq C and B cap C is empty.

If "A" and "B" are not effectively separable then they are effectively inseparable.

Examples

#Let "A" be the set of Godel numbers of Turing machines "M" such that on input "0" the machine "M" halts and outputs "0". Let "B" be the set of Godel numbers of Turing machines "M" such that on input "0" the machine "M" halts and outputs "1". Then "A" and "B" are effectively inseparable recursively enumerable sets.
#Let "T" be the set of (Godel numbers of) theorems provable from the axioms of Peano arithmetic, which is a recursively enumerable set, and let "R" be the set of negations of theorems of the axioms of Peano arithmetic, which is also recursively enumerable. Then "T" and "R" are effectively inseparable sets. A similar result would hold with any sufficiently strong axiom system in place of Peano arithmetic.

References

Soare, R. "Recursively enumerable sets and degrees." Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

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

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • Judaism — /jooh dee iz euhm, day , deuh /, n. 1. the monotheistic religion of the Jews, having its ethical, ceremonial, and legal foundation in the precepts of the Old Testament and in the teachings and commentaries of the rabbis as found chiefly in the… …   Universalium

  • Reverse mathematics — is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. The method can briefly be described as going backwards from the theorems to the axioms. This contrasts with the ordinary… …   Wikipedia

  • Europe, history of — Introduction       history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… …   Universalium

  • CMA-ES — stands for Covariance Matrix Adaptation Evolution Strategy. Evolution strategies (ES) are stochastic, derivative free methods for numerical optimization of non linear or non convex continuous optimization problems. They belong to the class of… …   Wikipedia

  • Christian theology — The Prophetess Anna, Rembrandt, 1631 See also: History of Christian theology and Outline of Christian theology Christian doctrine redirects here. For the United States Court case known by that name, see G.L. Christian and associates v. US.… …   Wikipedia

  • Viscoelasticity — is the property of materials that exhibit both viscous and elastic characteristics when undergoing deformation. Viscous materials, like honey, resist shear flow and strain linearly with time when a stress is applied. Elastic materials strain… …   Wikipedia

  • Neural network — For other uses, see Neural network (disambiguation). Simplified view of a feedforward artificial neural network The term neural network was traditionally used to refer to a network or circuit of biological neurons.[1] The modern usage of the term …   Wikipedia

  • operations research — the analysis, usually involving mathematical treatment, of a process, problem, or operation to determine its purpose and effectiveness and to gain maximum efficiency. [1940 45, Amer.] * * * Application of scientific methods to management and… …   Universalium

Share the article and excerpts

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