| dbo:abstract
|
- In der Berechenbarkeitstheorie und der mathematischen Logik misst der Turinggrad (auch Grad der Unlösbarkeit) einer Menge natürlicher Zahlen die algorithmische Unlösbarkeit der Menge. Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie, wo Mengen natürlicher Zahlen oft als Entscheidungsprobleme angesehen werden; der Turinggrad einer Menge gibt an, wie schwer das Entscheidungsproblem für die Menge ist. Zwei Mengen sind Turing-äquivalent, wenn sie den gleichen Grad der Unlösbarkeit haben; jeder Turinggrad ist eine Menge Turing-äquivalenter Mengen, sodass zwei Mengen genau dann in unterschiedlichen Turinggraden liegen, wenn sie nicht Turing-äquivalent sind. Außerdem sind die Turinggrade im folgenden Sinne partiell geordnet: Wenn der Turinggrad einer Menge kleiner als der Turinggrad einer Menge ist, dann kann jede (unberechenbare) Prozedur, die korrekt entscheidet, ob Zahlen in liegen, berechenbar in eine Prozedur umgewandelt werden, die korrekt entscheidet, ob Zahlen in liegen. In diesem Sinne korrespondiert der Turinggrad einer Menge mit dem Grad ihrer algorithmischen Unlösbarkeit. Die Turinggrade wurden 1944 von Emil Leon Post eingeführt, und viele grundlegende Resultate wurden 1954 von Stephen Cole Kleene und Post bewiesen. Die Turinggrade sind bis heute Gegenstand intensiver Forschung. Viele Beweise in diesem Gebiet benutzen eine Beweistechnik, die als Prioritätsmethode bekannt ist. (de)
- En informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. (fr)
- In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. (en)
- チューリング次数（～じすう、英: Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。 任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 のチューリング次数が集合 のチューリング次数よりも小さいならば、ある数が に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。 チューリング次数はエミール・ポスト(1944)によって導入され、多くの基本的な結果はスティーヴン・コール・クリーネとポスト(1954)によって確立された。それ以来、チューリング次数は主要な研究分野の一つとなっている。関連する証明では優先度法と呼ばれる技法がよく使われる。 (ja)
- Em ciência da computação e lógica matemática o grau de Turing ou grau de insolubilidade de um conjunto de números naturais mede o nível de insolubilidade algorítmica do conjunto. O conceito de grau de Turing é fundamental na teoria da computabilidade, onde conjuntos de números naturais são frequentemente considerados como , o grau de Turing de um conjunto diz o quão difícil é resolver o problema de decisão associado com o conjunto. Dois conjuntos são Turing equivalentes, se tiverem o mesmo nível de insolubilidade; cada grau de Turing é uma coleção de conjuntos Turing equivalentes, de modo que dois conjuntos estão em graus de Turing diferentes exatamente quando não são Turing equivalentes. Além disso, os graus de Turing são parcialmente ordenada de modo que, se o grau de Turing de um conjunto “X” é menor que o grau de Turing de um conjunto “Y”, então qualquer procedimento (computável) que correctamente decide se os números estão em “Y” pode ser convertido de maneira eficaz a um procedimento que corretamente decide se os números estão em “X”. É neste sentido que o grau de Turing de um conjunto corresponde ao seu nível de insolubilidade algorítmica. Os graus de Turing foram introduzidas por (1944), e muitos resultados fundamentais foram estabelecidos por Stephen Cole Kleene e Post (1954). Os graus de Turing têm sido uma área de intensa pesquisa desde então. Muitas provas na área fazem uso de uma técnica de prova conhecida como o método da prioridade. (pt)
- 不可解度，或图灵度（Turing degree），是数学逻辑的名词，尤其应用在可计算性理论中。 (zh)
- В інформатиці та математичній логіці Степінь Тюрінга (названа на честь Алана Тюрінга) або степінь нерозв'язності множини натуральних чисел вимірює рівень алгоритмічної нерозв'язності множини. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 20868 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- En informatique et en logique mathématique, le degré de Turing (nommé d'après Alan Turing) ou le degré d'insolubilité d'un ensemble d'entiers naturels mesure le niveau d'insolubilité algorithmique de l'ensemble. (fr)
- In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. (en)
- 不可解度，或图灵度（Turing degree），是数学逻辑的名词，尤其应用在可计算性理论中。 (zh)
- В інформатиці та математичній логіці Степінь Тюрінга (названа на честь Алана Тюрінга) або степінь нерозв'язності множини натуральних чисел вимірює рівень алгоритмічної нерозв'язності множини. (uk)
- In der Berechenbarkeitstheorie und der mathematischen Logik misst der Turinggrad (auch Grad der Unlösbarkeit) einer Menge natürlicher Zahlen die algorithmische Unlösbarkeit der Menge. Das Konzept des Turinggrades ist fundamental in der Berechenbarkeitstheorie, wo Mengen natürlicher Zahlen oft als Entscheidungsprobleme angesehen werden; der Turinggrad einer Menge gibt an, wie schwer das Entscheidungsproblem für die Menge ist. (de)
- チューリング次数（～じすう、英: Turing degree, degree of unsolvability）は、計算理論及び数理論理学に出現する次数であり、自然数の集合に対して付与され、その集合のアルゴリズム的な複雑さ（非可解性）の度合いを表す。名称はアラン・チューリングに因む。チューリング次数の概念は再帰理論と計算可能性理論において基本的である。これらの分野では、自然数の集合はそのまま決定問題の集合だと看做されることが多い。ある集合に付与されたチューリング次数は、その集合に関連付けられた決定問題を解くことがどの程度難しいかを示す。 任意の二つの集合間で非可解性の度合いが同等であるとき、それらはチューリング同値であると言う。個々のチューリング次数は、チューリング同値であるような一群の集合に対応する。二つの集合が相異なるチューリング次数に属するのは、正にそれらがチューリング同値では無い場合である。更に、チューリング次数は半順序を成すので、集合 のチューリング次数が集合 のチューリング次数よりも小さいならば、ある数が に含まれるかを正しく判定するあらゆる（計算不可能なものも含む）手続きは、ある数が に含まれるかを正しく判定する手続きに変換することができる。任意の集合のチューリング次数はこのような意味でその集合のアルゴリズム的な非可解性の度合いに対応する。 (ja)
- Em ciência da computação e lógica matemática o grau de Turing ou grau de insolubilidade de um conjunto de números naturais mede o nível de insolubilidade algorítmica do conjunto. O conceito de grau de Turing é fundamental na teoria da computabilidade, onde conjuntos de números naturais são frequentemente considerados como , o grau de Turing de um conjunto diz o quão difícil é resolver o problema de decisão associado com o conjunto. (pt)
|
| rdfs:label
|
- Turinggrad (de)
- Degré de Turing (fr)
- チューリング次数 (ja)
- Grau de Turing (pt)
- Turing degree (en)
- 不可解度 (zh)
- Степінь Тюрінга (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
