Вычисления с оракулом — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 1: Строка 1:
В теории вычислений и теории сложности Машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
+
В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Будем называть '''оракулом''' для языка <tex>A</tex> абстрактное вычислительное устройство, для которого постулируется возможность решить задачу о принадлежности некоторого слова языку <tex>A</tex> за <tex>O(1)</tex> времени.
+
Оракул — абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.
 
}}
 
}}
 
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.  
 
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.  
Строка 9: Строка 9:
 
== Сведение по Тьюрингу ==
 
== Сведение по Тьюрингу ==
  
В теории вычислимости, сведение по Тьюрингу задачи A к задаче B — это сведение, которое решает A, предполагая, что B уже известно. Это можно понимать как алгоритм, который может быть использован для решения A, если в его распоряжении имеются подпрограммы для решения B. Более формально, сведение по Тьюрингу является функцией, вычислимой машиной с оракулом для В.
+
В теории вычислимости сведение по Тьюрингу задачи A к задаче B — это сведение, которое решает A, предполагая, что B уже известно. Это можно понимать как алгоритм, который может быть использован для решения A, если в его распоряжении имеются подпрограммы для решения B. Более формально, сведение по Тьюрингу является функцией, вычислимой машиной с оракулом для В.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =

Текущая версия на 19:37, 4 сентября 2022

В теории вычислений и теории сложности "машиной с оракулом" называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.

Определение:
Оракул — абстракция, вычисляющая за [math]O(1)[/math] времени, верно ли, что [math]x[/math] принадлежит множеству [math]A[/math].

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math]. Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].

Сведение по Тьюрингу

В теории вычислимости сведение по Тьюрингу задачи A к задаче B — это сведение, которое решает A, предполагая, что B уже известно. Это можно понимать как алгоритм, который может быть использован для решения A, если в его распоряжении имеются подпрограммы для решения B. Более формально, сведение по Тьюрингу является функцией, вычислимой машиной с оракулом для В.

Определение:
Даны два множества натуральных чисел [math]A[/math] и [math]B[/math], тогда говорим, что [math]A[/math] сводится по Тьюрингу к [math]B[/math] ([math]A \leq_{T} B[/math]), если есть машина с оракулом [math]B[/math], которая вычисляет характеристическую функцию [math]A[/math]. В этом случае мы также говорим, что [math]A[/math] является [math]B[/math]-рекурсивным и [math]B[/math]-вычислимым.