Oracle Computing
В изчислителната теория и теорията на сложността, "оракулска машина" е абстрактна машина, предназначена да решава проблем с разрешимостта. Такава машина може да се разглежда като машина на Тюринг, пълна с оракул с неизвестни вътрешни елементи. Постулира се, че оракулът е способен да реши определени проблеми с разрешимостта в един цикъл на машината на Тюринг. Машината на Тюринг взаимодейства с оракула, като записва входни данни към оракула на неговата лента и след това го стартира за изпълнение. В една стъпка оракулът оценява функцията, изтрива входа и записва изхода на лента. Понякога машината на Тюринг се описва като имаща две ленти, една за входа на оракула и една за изхода.
| Определение: |
| Оракулът е абстракция, която изчислява за [math]O(1)[/math] време дали е вярно, че [math]x[/math] принадлежи към множеството [math]A[/math] . |
Информация за Тюринг[редактиране]
В теорията на изчислимостта редукцията на Тюринг на проблем A до проблем B е редукцията, която A решава, като приемем, че B вече е известен. Това може да се разбира като алгоритъм, който може да се използва за решаване на A, ако има рутинни процедури за решаване на B. По-формално, намаляването на Тюринг е функция, изчислена от машина с оракул за B.