Turing degree of a set is written .

Given a set , a set is called Turing hard for if for all . If additionally then is called Turing complete for .

Relation of Turing completeness to computational universality

Turing completeness, as just defined above, corresponds only partially to Turing completeness in the sense of computational universality. Specifically, a Turing machine is a universal Turing machine

1.Previous
3.Next