Maszyny Turinga z wyrocznią są użyteczne w badaniu relacji pomiędzy klasami złożoności P i NP, co wiąże się z nierozwiązanym dotychczas problemem P vs NP. W szczególności twierdzenie Bakera-Gilla-Solovaya mówi, że istnieją takie języki X i Y, że PX = NPX i PY ≠ NPY . Uważa się, że fakt ten świadczy o trudności problemu P vs NP, ponieważ pokazuje, że ten problem nie może zostać rozwiązany przy pomocy większości znanych technik dowodowych. Większość metod dowodowych to rozumowania, które relatywizują się, tzn. wykorzystują własności, które nie zmieniają się nawet, jeśli założymy, że każda maszyna Turinga w dowodzie ma dostęp do dowolnej, ale takiej samej wyroczni.
Zobacz też Niedeterministyczna maszyna Turinga Transformacja Turinga Maszyna Turinga
Przypisy
Bibliografia
Kategoria:Teoria obliczeń