Oracle machine (original) (raw)
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.
| Property | Value |
|---|---|
| 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) |
| dbo:wikiPageExternalLink | http://citeseer.ist.psu.edu/282397.html |
| dbo:wikiPageID | 22431 (xsd:integer) |
| dbo:wikiPageLength | 12109 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120745360 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Robert_M._Solovay dbr:Hartley_Rogers,_Jr. dbr:DLOGTIME dbr:Decision_problem dbr:Interactive_proof_system dbr:Space_hierarchy_theorem dbr:Computability_theory dbr:Cryptographic_hash_function dbr:Cryptography dbr:Christos_Papadimitriou dbr:NP-complete dbc:Turing_machine dbr:SIAM_Journal_on_Computing dbr:Arithmetical_hierarchy dbr:Complete_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbr:Function_problem dbr:Matroid_oracle dbr:Alan_Turing dbr:PSPACE dbr:Kolmogorov's_zero–one_law dbr:Provable_security dbr:Halting_problem dbr:Abstract_machine dbc:Computability_theory dbr:Juris_Hartmanis dbr:Black_box dbr:Black_box_group dbc:Computation_oracles dbr:Martin_Davis_(mathematician) dbr:Boolean_satisfiability_problem dbr:Polynomial_hierarchy dbr:Polynomial_time dbr:Indicator_function dbr:Michael_Sipser dbr:Turing_machine dbr:Undecidable_problem dbr:IP_(complexity) dbr:Robert_I._Soare dbr:Time_hierarchy_theorem dbr:Turing_reduction dbr:Random_oracle dbr:P_=_NP_problem dbr:Deterministic_Turing_machine |
| dbp:wikiPageUsesTemplate | dbt:For dbt:Main dbt:Short_description dbt:Isbn dbt:Black-box dbt:Issn |
| dcterms:subject | dbc:Turing_machine dbc:Computability_theory dbc:Computation_oracles |
| gold:hypernym | dbr:Machine |
| rdf:type | dbo:Software yago:WikicatModelsOfComputation yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| 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) |
| rdfs:label | Màquina oracle (ca) Orakel-Turingmaschine (de) Máquina oráculo (es) Oracle (machine de Turing) (fr) 神託機械 (ja) 신탁 기계 (ko) Oracle machine (en) Maszyna Turinga z wyrocznią (pl) Máquina oráculo (pt) Вычисления с оракулом (ru) Пророча машина (uk) 預言機 (zh) |
| owl:sameAs | freebase:Oracle machine yago-res:Oracle machine wikidata:Oracle machine dbpedia-ca:Oracle machine dbpedia-de:Oracle machine dbpedia-es:Oracle machine dbpedia-fa:Oracle machine dbpedia-fi:Oracle machine dbpedia-fr:Oracle machine dbpedia-he:Oracle machine dbpedia-ja:Oracle machine dbpedia-ko:Oracle machine dbpedia-pl:Oracle machine dbpedia-pt:Oracle machine dbpedia-ru:Oracle machine dbpedia-sr:Oracle machine dbpedia-tr:Oracle machine dbpedia-uk:Oracle machine dbpedia-zh:Oracle machine https://global.dbpedia.org/id/BsLT |
| prov:wasDerivedFrom | wikipedia-en:Oracle_machine?oldid=1120745360&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Oracle_machine |
| is dbo:wikiPageDisambiguates of | dbr:Oracle_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Oracle_(complexity) dbr:Machine_oracle dbr:Turing_oracle dbr:Oracle_(computability) dbr:Oracle_(computer_science) dbr:Oracle_(computing) dbr:Oracle_Machines dbr:Oracle_Turing_machine dbr:Oracle_algorithm dbr:Oracle_set dbr:Oracle_tape dbr:Relativization dbr:Baker-Gill-Solovay_theorem dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles |
| is dbo:wikiPageWikiLink of | dbr:Amplitude_amplification dbr:Proof_of_impossibility dbr:Quantum_complexity_theory dbr:Endgame_tablebase dbr:Entscheidungsproblem dbr:Enumeration_reducibility dbr:List_of_complexity_classes dbr:List_of_computability_and_complexity_topics dbr:Parity_P dbr:Alice_and_Bob dbr:Volume dbr:Descriptive_complexity_theory dbr:Deutsch–Jozsa_algorithm dbr:Induction_puzzles dbr:Interactive_proof_system dbr:List_of_mathematical_logic_topics dbr:Systems_of_Logic_Based_on_Ordinals dbr:Timeline_of_quantum_computing_and_communication dbr:♯P dbr:SL_(complexity) dbr:Generic_group_model dbr:Geometric_complexity_theory dbr:Oracle_(disambiguation) dbr:NP-easy dbr:Quantum_algorithm dbr:Convex_polytope dbr:Convex_volume_approximation dbr:Cook–Levin_theorem dbr:Arithmetical_hierarchy dbr:Berman–Hartmanis_conjecture dbr:Bernstein–Vazirani_algorithm dbr:Chosen-plaintext_attack dbr:Closed-world_assumption dbr:Complete_(complexity) dbr:Demand_oracle dbr:Feistel_cipher dbr:Function_problem dbr:PH_(complexity) dbr:Probabilistically_checkable_proof dbr:Matroid_oracle dbr:BPP_(complexity) dbr:BQP dbr:Admissible_ordinal dbr:Garbage_collection_(computer_science) dbr:Large_countable_ordinal dbr:Lattice_problem dbr:Alan_Turing dbr:Algorithmically_random_sequence dbr:Norman_Shapiro dbr:PP_(complexity) dbr:Differential_testing dbr:Digital_signature dbr:Formal_methods dbr:God's_algorithm dbr:Graph_isomorphism_problem dbr:Halting_problem dbr:Hypercomputation dbr:Advantage_(cryptography) dbr:Lance_Fortnow dbr:Black_box dbr:Black_box_group dbr:Block_cipher dbr:Hidden_shift_problem dbr:Hidden_subgroup_problem dbr:Polynomial_hierarchy dbr:Ciphertext_indistinguishability dbr:Circuits_over_sets_of_natural_numbers dbr:Grover's_algorithm dbr:Chaitin's_constant dbr:Message_authentication_code dbr:Turing_machine dbr:IP_(complexity) dbr:Turing_jump dbr:Low_(complexity) dbr:Pointclass dbr:Examples_of_data_mining dbr:NP-hardness dbr:Post's_theorem dbr:Polynomial_creativity dbr:Turing_reduction dbr:Ω-consistent_theory dbr:P_versus_NP_problem dbr:Pseudorandom_permutation dbr:Property_testing dbr:Random_oracle dbr:S2S_(mathematics) dbr:Oracle_(complexity) dbr:Machine_oracle dbr:Turing_oracle dbr:Oracle_(computability) dbr:Oracle_(computer_science) dbr:Oracle_(computing) dbr:Oracle_Machines dbr:Oracle_Turing_machine dbr:Oracle_algorithm dbr:Oracle_set dbr:Oracle_tape dbr:Relativization dbr:Baker-Gill-Solovay_theorem dbr:Computer_Science_Oracle dbr:Computer_Science_Oracles |
| is foaf:primaryTopic of | wikipedia-en:Oracle_machine |