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 decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.

PropertyValue
dbpprop:abstract
  • 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 decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.
  • 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 Turingmaschinen mit dem Halteproblem als Orakel können 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.
  • La máquina oracle en teoría tiene como finalidad la de estudiar la decisión de problemas. Puede verse como una máquina de Turing con una caja negra, llamada oracle. La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
  • Oraakkelikone on laskennan vaativuusteoriassa abstrakti kone, joka pystyy ratkaisemaan tiettyyn vaativuusluokkaan kuuluvia ongelmia. Oraakkelikonetta käytetään tutkittaessa eri vaativuusluokkien, kuten P ja NP, suhdetta.
  • En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing. On peut les voir comme une machine de Turing disposant d'une boîte noire, l'oracle, capable de résoudre un problème de décision en une seule opération. Ce problème peut être de n'importe quelle complexité.
  • 神託機械または預言機械（英: Oracle machine）は、計算複雑性理論や計算可能性理論における抽象機械の一種であり、決定問題の研究で使われる。チューリング機械にオラクル（oracle）と呼ばれるブラックボックスが付加されたものとして具体化され、そのブラックボックスは特定の決定問題を1ステップで決定可能である。その問題は任意の複雑性クラスに属する。チューリングマシンの停止問題のような決定不能な問題にも神託機械を想定することができる。
  • Kahinli Turing makinesi, klasik Turing makinesi ile aynı temelleri kullanarak çalışır: Bir veya birkaç şerit Şerit(ler)i okumak için kafa(lar) Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık Öte yandan, kahinli Turing makinesi özel bir duruma sahiptir: kahine soru durumu. Başka bir deyişle, geçiş tablosunda şu şekilde bir giriş bulunur: Güncel Okunan Yeni Yeni Durum Sembol Durum 1 Durum 2 dk s dk1 dk2 Bu durumda, dk durumunda s sembolü okunursa kahine gidilecektir. Kahin, makineyi sorunun cevabı evet ise dk1, hayır ise dk2 durumuna geçirecektir. Kahinin Turing makinesinin tüm şeritlerini okuma ve değiştirme hakkı vardır. Kahinli Turing makinesi, NP-complete problem indirgemesi yapılırken kullanılır, zira bir problemin (yani kahinin) başka bir problemin çözümünde nasıl kullanılabileceğini göstermektedir.
dbpprop:hasPhotoCollection
rdf:type
rdfs:comment
  • 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 decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used.
  • 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.
  • La máquina oracle en teoría tiene como finalidad la de estudiar la decisión de problemas. Puede verse como una máquina de Turing con una caja negra, llamada oracle. La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
  • Oraakkelikone on laskennan vaativuusteoriassa abstrakti kone, joka pystyy ratkaisemaan tiettyyn vaativuusluokkaan kuuluvia ongelmia. Oraakkelikonetta käytetään tutkittaessa eri vaativuusluokkien, kuten P ja NP, suhdetta.
  • En théorie de la complexité ou de la calculabilité, les machines de Turing avec oracle sont une variante des machines de Turing. On peut les voir comme une machine de Turing disposant d'une boîte noire, l'oracle, capable de résoudre un problème de décision en une seule opération. Ce problème peut être de n'importe quelle complexité.
  • Kahinli Turing makinesi, klasik Turing makinesi ile aynı temelleri kullanarak çalışır: Bir veya birkaç şerit Şerit(ler)i okumak için kafa(lar) Geçiş tablosunu ve Turing makinesinin o anki durumunu içeren bir iç mantık Öte yandan, kahinli Turing makinesi özel bir duruma sahiptir: kahine soru durumu.
rdfs:label
  • Oracle machine
  • Orakel-Turingmaschine
  • Máquina oracle
  • Oraakkelikone
  • Oracle (machine de Turing)
  • 神託機械
  • Kahinli Turing makinesi
owl:sameAs
skos:subject
foaf:page
is dbpprop:disambiguates of
is dbpprop:redirect of
is owl:sameAs of