Transformacja Turinga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Transformacja Turinga – redukcja pozwalająca „łatwo” rozwiązać problem A przy założeniu, że znane jest rozwiązanie problemu B. Nazwa pochodzi od nazwiska Alana Turinga.

Definicja formalna[edytuj | edytuj kod]

A \leqslant_T B, jeśli istnieje abstrakcyjna maszyna wyposażona w wyrocznię dla problemu B. Maszynę taką można sobie wyobrażać jako zwykłą maszynę abstrakcyjną, która dodatkowo potrafi rozwiązywać instancje problemu B.

Jeśli istnieje algorytm dla problemu B i A \leqslant_T B, to możemy napisać również algorytm dla problemu A.

Zobacz też[edytuj | edytuj kod]