Turing degree

Turing degree
Given a set of natural numbers, a measure of the level of algorithmic unsolvability of the set.
See Also: Turing equivalent

Wikipedia foundation.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • 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

  • Turing equivalence — may refer to:* Turing completeness, having computational power equivalent to a universal Turing machine * Turing degree equivalence (of sets), having the same level of unsolvability …   Wikipedia

  • Turing jump — In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is intuitively described as an operation that assigns to each decision problem X a successively harder decision problem X prime; with the property that X… …   Wikipedia

  • Turing reduction — In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to …   Wikipedia

  • Alan Turing — Turing redirects here. For other uses, see Turing (disambiguation). Alan Turing Turing at the time of his election to Fellowship of the Royal Society …   Wikipedia

  • Degree of truth — In standard mathematics, propositions can typically be considered unambiguously true or false. For instance, the proposition zero belongs to the set { 0 } is regarded as simply true; while the proposition one belongs to the set { 0 } is regarded… …   Wikipedia

  • Turing test — /ˈtjurɪŋ tɛst/ (say tyoohring test) noun a test designed to demonstrate that a machine can appear to have human intelligence to the degree that a human being engaged in remote communication with the machine and another human being cannot… …  

  • PA degree — In recursion theory, a mathematical discipline, a PA degree is a Turing degree that computes a complete extension of Peano arithmetic (Jockusch 1987). These degrees are closely related to fixed point free (DNR) functions, and have been thoroughly …   Wikipedia

  • Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… …   Wikipedia

  • Reverse Turing test — The term reverse Turing test has no single clear definition, but has been used to describe various situations based on the Turing test in which the objective and/or one or more of the roles have been reversed between computers and… …   Wikipedia

Share the article and excerpts

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