Transformacja Turinga: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
zobacz też |
poprawienie linku |
||
Linia 3:
== Definicja formalna ==
<math>A \leqslant_T B</math>, jeśli istnieje abstrakcyjna [[maszyna Turinga z wyrocznią|maszyna]] wyposażona w wyrocznię dla problemu ''B''. Maszynę taką można sobie wyobrażać jako zwykłą [[maszyna abstrakcyjna|maszynę abstrakcyjną]], która dodatkowo potrafi rozwiązywać [[Wystąpienie (teoria obliczeń)|instancje]] problemu ''B''.
Jeśli istnieje [[algorytm]] dla problemu ''B'' i <math>A \leqslant_T B</math>, to możemy napisać również algorytm dla problemu ''A''.
| |||