1.Previous
3.Next

study of the Turing jump. Given a set A, the Turing jump of A is a set of natural numbers encoding a solution to the halting problem for oracle Turing machines running with oracle A. The Turing jump of any set is always of higher Turing degree than the original set, and a theorem of Friedburg shows that any set that computes the halting problem can be obtained as the Turing jump of another set. Post's theorem establishes a close relationship between the Turing jump

1.Previous
3.Next