Godel numbering and Turing jump

187 Views Asked by At

Given a set $X$ and a Gödel numbering $φ_i^X$ of the $X$-computable functions, the Turing jump $X'$ of $X$ is defined as

$X'= \{x \mid \varphi_x^X(x) \ \mbox{is defined} \}.$

OK. But then it says that Godel numbering of X-computable functions - so isn't $x$ basically confined as set $X$? Or am I wrong here...

It's OK just to show the equivalence of above with defining $X'$ as "with elements of $X'$ halting problem of elements of $X$ can be solved."

1

There are 1 best solutions below

0
On

I don't really understand the question (for example "confined as $X$"), but I sense that there may be some misunderstanding of the notion of $X$-computable. This notion refers to functions, from natural numbers to natural numbers, that are computable by a Turing machine equipped with an oracle for the set $X$. The inputs, the outputs, and the Gödel numbers are still just natural numbers; they need not be in $X$. So $X'$ is exactly analogous to the usual halting set, with only this one difference, that instead of Turing machines, one uses Turing machines equipped with an $X$-oracle.