Turing reduction (original) (raw)
Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyrocznią B, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A . Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A =T B. Podobnie, jeżeli A ≤T B i nie A =T B to A <T B .
| Property | Value |
|---|---|
| dbo:abstract | In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving B. The concept can be analogously applied to function problems. If a Turing reduction from to exists, then every algorithm for can be used to produce an algorithm for , by inserting the algorithm for at each place where the oracle machine computing queries the oracle for . However, because the oracle machine may query the oracle a large number of times, the resulting algorithm may require more time asymptotically than either the algorithm for or the oracle machine computing . A Turing reduction in which the oracle machine runs in polynomial time is known as a Cook reduction. The first formal definition of relative computability, then called relative reducibility, was given by Alan Turing in 1939 in terms of oracle machines. Later in 1943 and 1952 Stephen Kleene defined an equivalent concept in terms of recursive functions. In 1944 Emil Post used the term "Turing reducibility" to refer to the concept. (en) チューリング還元（チューリングかんげん、英: Turing reduction）は、計算量理論におけるの一種である。アラン・チューリングの名がつけられた還元であり、問題 A が問題 B にチューリング還元されるとは、B が容易に解けると仮定したときに A が容易に解けることを意味する（Rogers 1967、Soare 1987）。より厳密に言えば、B を神託として備えた神託機械によってAが計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。 A から B へのチューリング還元が存在するとき、B を解くあらゆるアルゴリズムは A を解くアルゴリズムを作成するのに使うことが可能である。これは、 A を計算する神託機械が B に関する神託を質問する箇所に B のアルゴリズムを挿入することで実現される。しかし、この神託機械は何回も神託を訊ねる可能性があり、A のアルゴリズムは時間的にも空間的にも B のアルゴリズムよりも計算資源を多く必要とする可能性がある。 アラン・チューリング（1939年）は、神託機械を用いて相対計算可能性（当時は相対還元可能性と称していた）に初めて形式的な定義を与えた。1943年と1952年、スティーヴン・コール・クリーネは同様の概念を帰納的関数を用いて定義した。1944年、エミール・ポストはこの概念を表すのに初めて「チューリング還元可能性（Turing reducibility）」という用語を使った。 (ja) Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyrocznią B, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A . Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A =T B. Podobnie, jeżeli A ≤T B i nie A =T B to A <T B . (pl) В теории вычислимости редукция Тьюринга (также известная как редукция Кука ) от проблемы A к проблеме B - это редукция, которая решает A, при условии, что решение B уже известно. Ее можно понимать как алгоритм, который можно было бы использовать для решения A, если бы он имел доступную подпрограмму для решения B. Более формально редукция Тьюринга - это функция, вычисляемая машиной-оракулом с оракулом для B. Первое формальное определение относительной вычислимости, которое тогда называлось относительной сводимостью, было дано Аланом Тьюрингом в 1939 году в терминах машин-оракулов. Позже, в 1943 и 1952 годах, Стивен Клини определил эквивалентное понятие в терминах рекурсивных функций. В 1944 году Эмиль Пост использовал термин «сводимость Тьюринга» для обозначения этой концепции. (ru) Na Teoria da Computação, a redução de Turing de um problema A para um problema B, nomeado após Alan Turing, é uma redução que resolve A, assumindo que B já é conhecido(Rogers 1967, Soare 1987). Esta pode ser entendida como um algoritmo que pode ser usado para resolver A se este for for válido como uma sub-rotina que resolve B. De uma maneira mais formal, a redução de Turing é uma função computável por uma máquina Turing com um oráculo para B. A redução de turing pode ser aplicada tanto para problemas de decisão quanto para problemas problemas de função. Se uma redução de Turing de A para B existe, então todo algoritmo que resolve B pode ser usado para produzir um algoritmo que resolve A, inserindo o algoritmo que resolve B em cada lugar onde a máquina de Turing com um oráculo, ao computar A, consulta o oráculo de B. Entretanto, já que a máquina Turing com oráculo pode fazer um grande número de consultas ao oráculo, o algoritmo resultante pode requerer mais tempo do que o normal do que qualquer M ou máquina Turing com oráculo e pode necessitar de tanto espaço quanto os dois juntos. A primeira definição formal de uma computação relativa, depois chamada de redutibilidade relativa, foi dada por Alan Turing em 1939 na definição da máquina de Turing com oráculo. Depois, em 1943 e 1952, Stephen Kleene definiu um conceito equivalente sobre a definição de funções recursivas. Em 1944 Emil Post usou a definição de "Redução de Turing" para se referir ao conceito. (pt) 圖靈歸約是可计算性理论中的一種歸約，若問題A可圖靈歸約成問題B，是指若問題B的解答已經知道（Rogers 1967, Soare 1987），就可以解問題A，也可以解釋為若一個演算法可以用來處理問題B，就可以處理問題A。較正式的說法，可被圖靈歸約成問題B的問題是指若存在問題B的預言機，就可以求解的問題集合。圖靈歸約可以用在決定性問題及功能性問題。 (zh) |
| dbo:wikiPageExternalLink | http://projecteuclid.org/download/pdf_1/euclid.bams/1183505800 https://www.cis.upenn.edu/~jean/home.html https://www.cl.cam.ac.uk/teaching/2122/CompTheory/comt-notes.pdf http://www.ams.org/notices/200610/whatis-davis.pdf https://xlinux.nist.gov/dads/HTML/turingredctn.html |
| dbo:wikiPageID | 1188375 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-he:רדוקציה_חישובית |
| dbo:wikiPageLength | 12108 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116001304 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbr:Algorithm dbc:Reduction_(complexity) dbr:Peano_arithmetic dbr:Decision_problem dbr:Computability_theory dbr:Computable_function dbr:Constructible_universe dbr:Notices_of_the_American_Mathematical_Society dbr:Oracle_machine dbr:Church–Turing_thesis dbr:Equivalence_class dbr:Arithmetical_set dbr:Stephen_Kleene dbr:Subroutine dbr:Computable_set dbr:Computational_complexity_theory dbr:Function_problem dbr:P_(complexity) dbr:Many-one_reduction dbr:Total_order dbr:Well-founded dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:Alan_Turing dbr:PDF dbr:Halting_problem dbr:Smn_theorem dbc:Alan_Turing dbr:Indicator_function dbr:Recursive_ordinal dbr:Recursively_enumerable_set dbr:Undecidable_problem dbr:Universal_Turing_machine dbr:Turing_jump dbr:Mu-recursive_function dbr:Partial_order dbr:Turing_degree dbr:Turing_completeness dbr:Emil_Post dbr:Hyperarithmetical_hierarchy dbr:Karp_reduction dbr:Truth_table_reduction |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Cite_journal dbt:Efn dbt:Notelist dbt:Short_description dbt:Isbn |
| dcterms:subject | dbc:Reduction_(complexity) dbc:Alan_Turing |
| gold:hypernym | dbr:Reduction |
| rdf:type | owl:Thing dbo:Album |
| rdfs:comment | Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyrocznią B, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A . Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A =T B. Podobnie, jeżeli A ≤T B i nie A =T B to A <T B . (pl) 圖靈歸約是可计算性理论中的一種歸約，若問題A可圖靈歸約成問題B，是指若問題B的解答已經知道（Rogers 1967, Soare 1987），就可以解問題A，也可以解釋為若一個演算法可以用來處理問題B，就可以處理問題A。較正式的說法，可被圖靈歸約成問題B的問題是指若存在問題B的預言機，就可以求解的問題集合。圖靈歸約可以用在決定性問題及功能性問題。 (zh) In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving B. The concept can be analogously applied to function problems. (en) チューリング還元（チューリングかんげん、英: Turing reduction）は、計算量理論におけるの一種である。アラン・チューリングの名がつけられた還元であり、問題 A が問題 B にチューリング還元されるとは、B が容易に解けると仮定したときに A が容易に解けることを意味する（Rogers 1967、Soare 1987）。より厳密に言えば、B を神託として備えた神託機械によってAが計算可能であることである。チューリング還元は決定問題にも関数問題にも適用できる。 A から B へのチューリング還元が存在するとき、B を解くあらゆるアルゴリズムは A を解くアルゴリズムを作成するのに使うことが可能である。これは、 A を計算する神託機械が B に関する神託を質問する箇所に B のアルゴリズムを挿入することで実現される。しかし、この神託機械は何回も神託を訊ねる可能性があり、A のアルゴリズムは時間的にも空間的にも B のアルゴリズムよりも計算資源を多く必要とする可能性がある。 (ja) Na Teoria da Computação, a redução de Turing de um problema A para um problema B, nomeado após Alan Turing, é uma redução que resolve A, assumindo que B já é conhecido(Rogers 1967, Soare 1987). Esta pode ser entendida como um algoritmo que pode ser usado para resolver A se este for for válido como uma sub-rotina que resolve B. De uma maneira mais formal, a redução de Turing é uma função computável por uma máquina Turing com um oráculo para B. A redução de turing pode ser aplicada tanto para problemas de decisão quanto para problemas problemas de função. (pt) В теории вычислимости редукция Тьюринга (также известная как редукция Кука ) от проблемы A к проблеме B - это редукция, которая решает A, при условии, что решение B уже известно. Ее можно понимать как алгоритм, который можно было бы использовать для решения A, если бы он имел доступную подпрограмму для решения B. Более формально редукция Тьюринга - это функция, вычисляемая машиной-оракулом с оракулом для B. (ru) |
| rdfs:label | Turing reduction (en) チューリング還元 (ja) Transformacja Turinga (pl) Redução de Turing (pt) Редукция Тьюринга (ru) 圖靈歸約 (zh) |
| owl:sameAs | freebase:Turing reduction http://d-nb.info/gnd/4477590-8 wikidata:Turing reduction dbpedia-fa:Turing reduction dbpedia-ja:Turing reduction dbpedia-pl:Turing reduction dbpedia-pt:Turing reduction dbpedia-ru:Turing reduction dbpedia-zh:Turing reduction https://global.dbpedia.org/id/49kEh |
| prov:wasDerivedFrom | wikipedia-en:Turing_reduction?oldid=1116001304&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Turing_reduction |
| is dbo:knownFor of | dbr:Alan_Turing |
| is dbo:wikiPageRedirects of | dbr:Cook_reduction dbr:Turing-reducible dbr:Turing_complete_(reduction) dbr:Turing_complete_set dbr:Turing_completeness_(reduction) dbr:Turing_reducibility dbr:Turing_reducible dbr:Relative_computability dbr:A-computable dbr:A-recursive_set dbr:Co-A-recursive_set |
| is dbo:wikiPageWikiLink of | dbr:Preorder dbr:Enumeration_reducibility dbr:Cook_reduction dbr:Algorithm dbr:PSPACE-complete dbr:♯P-complete dbr:♯P-completeness_of_01-permanent dbr:SL_(complexity) dbr:Oracle_machine dbr:Constant-recursive_sequence dbr:Martin_measure dbr:Berman–Hartmanis_conjecture dbr:Combinatorial_optimization dbr:Complement_(complexity) dbr:Computability_logic dbr:Computation_in_the_limit dbr:Friedberg–Muchnik_theorem dbr:Mahaney's_theorem dbr:Sparse_language dbr:Many-one_reduction dbr:Matroid_oracle dbr:K-trivial_set dbr:Log-space_reduction dbr:Polynomial-time_reduction dbr:Truth-table_reduction dbr:Alan_Turing dbr:Algorithmically_random_sequence dbr:Legacy_of_Alan_Turing dbr:Reduction_(complexity) dbr:Reductionism dbr:Hyperarithmetical_theory dbr:Reduction_(computability_theory) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_things_named_after_Alan_Turing dbr:Post's_theorem dbr:Polynomial-time_counting_reduction dbr:Simple_set dbr:Turing-reducible dbr:Turing_complete_(reduction) dbr:Turing_complete_set dbr:Turing_completeness_(reduction) dbr:Turing_reducibility dbr:Turing_reducible dbr:Relative_computability dbr:A-computable dbr:A-recursive_set dbr:Co-A-recursive_set |
| is foaf:primaryTopic of | wikipedia-en:Turing_reduction |