Transformacja Turinga

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 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]