| 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)
|
| 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)
|
