Transformacja Turinga
Z Wikipedii
W teorii złożoności obliczeniowej transformacją Turinga problemu A do problemu B nazywamy (na cześć Alana Turinga) redukcję pozwalającą "łatwo" rozwiązać problem A przy założeniu, że znamy rozwiązanie problemu B.
Bardziej formalnie 
, 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 , to możemy napisać również algorytm dla problemu A.
zobacz też: Redukcja beta
