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 ^[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

• 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ż

• redukcja beta
• problem NP-trudny
• Maszyna Turinga z wyrocznią

Przypisy

Bibliografia

• Dexter C. Kozen: Automata and Computability. Springer, 1997. ISBN 0-387-94907-0.
• MartinM. Davis MartinM., What is...Turing Reducibility? [PDF], „Notices of the American Mathematical Society”, 10, 53, s. 1218–1219 .???