| dbo:abstract
|
- En teoria de la complexitat, una màquina oracle és màquina abstracta utilitzada per estudiar els problemes de decisió. Es pot veure com una màquina de Turing amb una caixa negra, anomenat oracle, que és capaç de solucionar certs problemes de decisió amb una sola operació. El problema pot ser de qualsevol classe de complexitat. Inclús es poden fer servir problemes que , com el problema de la parada. (ca)
- Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine Black-Box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der Begriff der Orakel-Turingmaschine dient in der Theoretischen Informatik dazu, Hierarchien von Berechenbarkeiten und Komplexitäten zu definieren und deren Eigenschaften zu studieren. Durch geeignete Orakel kann man die Berechenbarkeit verstärken oder die Komplexität verringern. Zum Beispiel können Turingmaschinen mit dem Halteproblem als Orakel das Halteproblem für Turingmaschinen lösen. Turingmaschinen mit SAT als Orakel können jedes Problem aus NP in polynomialer Zeit lösen. Orakel werden auch verwendet, um Nichtdeterminismus deterministisch zu modellieren. Eine nichtdeterministische Turingmaschine kann nämlich als Schar von deterministischen Orakel-Turingmaschinen wiedergegeben werden. Der Scharparameter, das Orakel, drückt dabei die Folge der nichtdeterministischen Entscheidungen aus. (de)
- En teoría de la complejidad y en la teoría de la computabilidad, una máquina oráculo es una máquina abstracta usada para estudiar problemas de decisión. Puede ser visualizada como una máquina de Turing con una caja negra, llamada oráculo, la cual puede decidir ciertos problemas de decisión en una simple operación. El problema puede ser cualquier clase de complejidad. Incluso pueden usarse problemas indecidibles, como el problema de la parada. (es)
- In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used. (en)
- En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt. Les machines de Turing avec oracle servent notamment à définir la hiérarchie polynomiale ou la hiérarchie arithmétique. (fr)
- 신탁 기계(神託機械, oracle machine)는 판정 문제를 연구하는 데 사용하는 추상 기계로, 일반적인 튜링 기계에 '신탁'(神託, oracle)이라는 블랙박스를 붙여놓은 것이라고 생각할 수 있다. 이때 신탁은 어떤 판정문제를 단 한번의 동작으로 풀 수 있는 장치이다. 신탁이 풀 수 있는 문제는 모든 복잡도 종류에 해당하기 때문에, 심지어 정지 문제 같은 도 풀 수 있다. (ko)
- 神託機械（しんたくきかい、英: oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。 (ja)
- Maszyna Turinga z wyrocznią – w teorii obliczeń abstrakcyjny model stosowany w celu badania problemów decyzyjnych. Maszynę Turinga z wyrocznią można traktować jako wielotaśmową maszynę Turinga z wyróżnioną, przeznaczoną tylko do odczytu taśmą (zwaną taśmą wyroczni), na której zapisany jest nieskończony ciąg symboli (zwany wyrocznią). Pod każdym innym względem maszyna Turinga z wyrocznią działa jak zwykła maszyna Turinga. Jeżeli zawartość taśmy wyroczni składa się wyłącznie z symboli zerowych, to taka maszyna jest zwykłą wielotaśmową maszyną Turinga. Część autorów podaje alternatywną definicję, w której zbiór stanów maszyny rozszerzony jest o stany dodatkowe {qask,qyes,qno} związane z obsługą wyroczni. Odwołanie do wyroczni polega na zapisaniu słowa na taśmie wyroczni i wywołaniu stanu qask, co skutkuje przejściem do stanu qyes lub qno w zależności od rozwiązania problemu decyzyjnego, o które pytana jest wyrocznia. Wyrocznia jest więc równoważna zbiorowi słów (językowi), dla których maszyna przechodzi do stanu qyes. (pl)
- Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão. Ela pode ser vista como uma máquina de Turing com uma caixa preta, chamada de oráculo, que é capaz de decidir alguns problemas de decisão em uma única operação. O problema pode ser de qualquer classe de complexidade. Até mesmo problemas indecidíveis, como o problema da parada, podem ser decididos nela. (pt)
- В теорії складності і теорії обчислюваності, пророча машина (англ. oracle machine) — це абстрактний автомат використовний для вивчення проблем вибору. Його можна зобразити як машину Тюрінга з чорною скринею, званою оракулом, яка здатна розв'язувати певні проблеми вибору за одну дію. Проблема може бути будь-якого класу складності. Можна використовувати навіть нерозв'зні проблеми, такі як проблема зупинки. (uk)
- 在计算复杂度理论与可计算性理论中，预言机（英語：Oracle Machine），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具備在一次运算之內解答特定问题的黑盒子（又稱為预言者）的图灵机；該问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。 (zh)
- Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.Постулируется, что оракул способен «угадать» решение проблемы разрешимости за одно обращение (один такт вызывающей его машины Тьюринга), после чего (машине Тьюринга) останется лишь это решение проверить. (ru)
|
| rdfs:comment
|
- En teoria de la complexitat, una màquina oracle és màquina abstracta utilitzada per estudiar els problemes de decisió. Es pot veure com una màquina de Turing amb una caixa negra, anomenat oracle, que és capaç de solucionar certs problemes de decisió amb una sola operació. El problema pot ser de qualsevol classe de complexitat. Inclús es poden fer servir problemes que , com el problema de la parada. (ca)
- En teoría de la complejidad y en la teoría de la computabilidad, una máquina oráculo es una máquina abstracta usada para estudiar problemas de decisión. Puede ser visualizada como una máquina de Turing con una caja negra, llamada oráculo, la cual puede decidir ciertos problemas de decisión en una simple operación. El problema puede ser cualquier clase de complejidad. Incluso pueden usarse problemas indecidibles, como el problema de la parada. (es)
- In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a single operation. The problem can be of any complexity class. Even undecidable problems, such as the halting problem, can be used. (en)
- En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing disposant d'une boîte noire, un oracle, capable de résoudre un problème de décision en une seule opération élémentaire. En particulier, l'oracle peut résoudre en temps constant un problème indécidable comme le problème de l'arrêt. Les machines de Turing avec oracle servent notamment à définir la hiérarchie polynomiale ou la hiérarchie arithmétique. (fr)
- 신탁 기계(神託機械, oracle machine)는 판정 문제를 연구하는 데 사용하는 추상 기계로, 일반적인 튜링 기계에 '신탁'(神託, oracle)이라는 블랙박스를 붙여놓은 것이라고 생각할 수 있다. 이때 신탁은 어떤 판정문제를 단 한번의 동작으로 풀 수 있는 장치이다. 신탁이 풀 수 있는 문제는 모든 복잡도 종류에 해당하기 때문에, 심지어 정지 문제 같은 도 풀 수 있다. (ko)
- 神託機械（しんたくきかい、英: oracle machine）または預言機械（よげんきかい）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリングマシンに神託（oracle）と呼ばれるブラックボックスが付加されたものであり、そのブラックボックスは特定の決定問題を1ステップで決定可能である。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。 (ja)
- Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão. Ela pode ser vista como uma máquina de Turing com uma caixa preta, chamada de oráculo, que é capaz de decidir alguns problemas de decisão em uma única operação. O problema pode ser de qualquer classe de complexidade. Até mesmo problemas indecidíveis, como o problema da parada, podem ser decididos nela. (pt)
- В теорії складності і теорії обчислюваності, пророча машина (англ. oracle machine) — це абстрактний автомат використовний для вивчення проблем вибору. Його можна зобразити як машину Тюрінга з чорною скринею, званою оракулом, яка здатна розв'язувати певні проблеми вибору за одну дію. Проблема може бути будь-якого класу складності. Можна використовувати навіть нерозв'зні проблеми, такі як проблема зупинки. (uk)
- 在计算复杂度理论与可计算性理论中，预言机（英語：Oracle Machine），又称谕示机，是一种抽象电脑，用来研究决定型问题。可以被视为具備在一次运算之內解答特定问题的黑盒子（又稱為预言者）的图灵机；該问题可以是任何复杂度类，甚至可以是不可判定问题，像是停机问题。 (zh)
- Вычисления с оракулом — вычисление с помощью машины Тьюринга, дополненной оракулом с неизвестным внутренним устройством.Постулируется, что оракул способен «угадать» решение проблемы разрешимости за одно обращение (один такт вызывающей его машины Тьюринга), после чего (машине Тьюринга) останется лишь это решение проверить. (ru)
- Eine Orakel-Turingmaschine ist eine Turingmaschine, die mit einem Orakel verbunden ist. Bildhaft kann man sich ein Orakel als eine Black-Box vorstellen, die von der Turingmaschine befragt werden kann und ein Problem in einem Schritt löst. Der Begriff der Orakel-Turingmaschine dient in der Theoretischen Informatik dazu, Hierarchien von Berechenbarkeiten und Komplexitäten zu definieren und deren Eigenschaften zu studieren. (de)
- Maszyna Turinga z wyrocznią – w teorii obliczeń abstrakcyjny model stosowany w celu badania problemów decyzyjnych. Maszynę Turinga z wyrocznią można traktować jako wielotaśmową maszynę Turinga z wyróżnioną, przeznaczoną tylko do odczytu taśmą (zwaną taśmą wyroczni), na której zapisany jest nieskończony ciąg symboli (zwany wyrocznią). Pod każdym innym względem maszyna Turinga z wyrocznią działa jak zwykła maszyna Turinga. Jeżeli zawartość taśmy wyroczni składa się wyłącznie z symboli zerowych, to taka maszyna jest zwykłą wielotaśmową maszyną Turinga. (pl)
|
