Transformacja Turinga
Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyrocznią B, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A . Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A =T B. Podobnie, jeżeli A ≤T B i nie A =T B to A <T B .
Transformacja Turinga (inaczej redukcja Turinga) – w teorii obliczeń relacja pomiędzy językami A i B. Mówi się, że język A jest turingowsko redukowalny do języka B (A ≤T B) jeżeli istnieje taka maszyna Turinga z wyrocznią B, że w skończonej liczbie kroków rozstrzyga przynależność słowa do A [1].
Jeżeli dla pewnych A, B ⊆ Σ* spełniona jest relacja A ≤T B i B ≤T A to A =T B. Podobnie, jeżeli A ≤T B i nie A =T B to A <T B [2].
Własności
[edytuj | edytuj kod]- Relacja ≤T jest przechodnia. Jeżeli A ≤T B i B ≤T C to A ≤T C [1]
- Każdy zbiór jest w relacji ≤T z własnym dopełnieniem (wystarczy zanegować dane z wyroczni) [1]
- Każdy zbiór rekurencyjny jest w relacji ≤T z dowolnym zbiorem (przynależność słowa do zbioru rekurencyjnego z definicji jest algorytmicznie sprawdzalna w skończonej liczbie kroków, więc obecność wyroczni może być zignorowana)
- Relacja ≤T nie jest częściowym porządkiem (A =T B nie implikuje A = B).
- Relacja ≤T nie jest liniowym porządkiem (istnieją takie A i B, że nie jest spełnione ani A ≤T B ani B ≤T A).
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]Bibliografia
[edytuj | edytuj kod]- Dexter C. Kozen: Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.
- Martin Davis, What is...Turing Reducibility? [PDF], „Notices of the American Mathematical Society”, 10, 53, s. 1218–1219.