请输入您要查询的字词:

 

单词 Oracle
释义

oracle


An oracle is a way to allow Turing machinesMathworldPlanetmath access to information they cannot necessarily calculate. It makes it possible to consider whether solving one problem would make it possible to solve another problem, and therefore to ask whether one problem is harder than another.

If T is a Turing machine and π is a problem (either a search problem or a decision problemMathworldPlanetmath) with appropriate alphabetMathworldPlanetmath then Tπ denotes the machine which runs T using π as an oracle.

A Turing machine with an oracle has three special states ?, y and n. Whenever Tπ enters state ? it queries the oracle about x, the series of non-blank symbols to the right of the tape head. If π is a decision problem then the machine immediately changes to state y if in xπ and n otherwise. If π is a search problem then it switches to state n if there is no z such that π(x,z) and to state y is there is such a z. In the latter case the section of the tape containing x is changed to contain z.

In either case, the oracle allows the machine to behave as if it could solve π, since each time it accesses the oracle, the result is the same as a machine which solves π.

Alternate but equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath definitions use a special tape to contain the query and response.

Clearly if LL then L(TL) may not be equal to L(TL).

By definition, if T is a Turing machine appropriate for a complexity classPlanetmathPlanetmath 𝒞 then TL is a 𝒞 Cook reduction of L(TL) to L.

If 𝒞 is a complexity class then T𝒞 is a complexity class with T𝒞={LL=L(TC)C𝒞}. If 𝒟 is another complexity class then 𝒟𝒞={LLT𝒞L(T)𝒟}.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:06:43