Turing Jump

The operator is called a ''jump operator'' because it increases the Turing Degree of the "problem" ''X''. That is, the problem ''X''′ is not Turing Reducible to ''X''. The Turing jump operator can be used to construct the Arithmetical Hierarchy of successively more powerful oracle machines and their associated halting problems.

DEFINITION

Given a set ''X'' and a Gödel Numbering

arphi_i^X

of the ''X''-computable functions, the Turing jump ''X''′ for ''X'' is defined as

:

X':= \{x \mid arphi_x^X(x) \, \mathrm{is\;defined}\}.

The n-th Turing jump ''X''^(''n'') is defined inductively by
:

X^{(0)} := X, \quad X^{(n+1)}:=(X^{(n)})'.

EXAMPLES

$K_arphi \equiv \emptyset'$ , the Turing jump of the empty set, is equivalent to the Halting Problem .

$\emptyset^{(n)}$ is M-complete in the collection $\Sigma_n$ in the Arithmetical Hierarchy

PROPERTIES

''X''′ is ''X''- Recursively Enumerable but not ''X''- Recursive .

''A'' is Turing Equivalent to ''B'' if and only if ''A''′ is Turing equivalent to ''B''′.

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT TURING JUMP

	recursion theory

Information About

Turing Jump