2

Prove that there is an n such that $W_n$ = {$2n, . . . , 2n + n^2$}

Now I don't know where to start with this question, how can I go about answering it? Would I construct a computable function that has that domain? What is that domain? I'm not sure I understand the question properly.

$W_n$ is the domain of a partial computable function with godel number n, is that right?

Ok, heres what I have so far with the recursion theorem:

define \begin{equation} g(x,y)=\begin{cases} 1, & \text{if $2x\le y \le 2x+x^2$}.\\ ↑, & \text{otherwise}. \end{cases} \end{equation}

Say g has an index e, such that $g = \varphi_e$

By S-M-N theorem we have a total computable $\varphi_{s(x)}(y) =\varphi_e(x,y)$.

Then we have $\varphi_{s(x)}$ = $\varphi_x$ fixed point by the recursion theorem

$\varphi_x$ has domain {$2x,...,2x+x^2$}, therefore such an n=x exists.

straykiwi
  • 135
  • 1
  • 7
  • Yes, $W_{n}$ is the domain of the $n$-th (under some fixed Gödel numbering) partial computable function. – Quinn Culver May 01 '13 at 15:22
  • The recursion theorem doesn't apply to your $f$ since it's not total. The point of the recursion theorem is that the function should be acting on indices; i.e. you want a function that outputs (the index of) a program. – Quinn Culver May 01 '13 at 23:28
  • And by the way, (even though it's not a good choice) your $f$ has a Gödel number because it's computable. Showing that it's computable is either tedious or easy, depending upon whether you can invoke the Church-Turing thesis. – Quinn Culver May 01 '13 at 23:31
  • I'm a bit confused. If I choose a total f, won't that mean f is defined on the entire domain, not a small subset 2n<=x<=2n+n^2 ? – straykiwi May 01 '13 at 23:48
  • The (index of the) function output by $f$ might not be total. Remember, $f$ should output a program (aka function), which is really just an index. – Quinn Culver May 01 '13 at 23:52
  • What about what I have now? – straykiwi May 02 '13 at 01:57
  • What you have now is still incorrect since you need $\varphi_{x}$ to have domain ${2x,\ldots,2x+x^{2}}$. You're very close though! – Quinn Culver May 02 '13 at 04:34
  • Hmm, should I swap it around to 2x <= y <= 2x + x^2 in g and leave the rest the same? I can't see the error, what is it's current domain? – straykiwi May 02 '13 at 06:16
  • Did you try swapping like that? What happens? – Quinn Culver May 02 '13 at 15:04
  • Looks good now, homie. – Quinn Culver May 02 '13 at 22:52

2 Answers2

1

Hint: Use the recursion theorem.

Quinn Culver
  • 4,471
  • Thanks, good advice. I've updated my question to show my progress so far using the recursion theorem, can you give another hint please? – straykiwi May 01 '13 at 23:23
1

Define

$\Psi(x,y) = \begin{cases} 0 & \quad 2x \leq y \leq 2x + x^2 \\ \uparrow & \quad \text{otherwise} \end{cases}$

It is clear that $\Psi$ is partial computable. By the s-m-n theorem, there exists a computable function $f$ such that

$\Psi(x,y) = \Phi_{f(x)}(y)$

By the recursion theorem, there exists a $n$ such that

$\Phi_{f(n)} = \Phi_n$

Therefore

$\Phi_n(y) = \Phi_{f(n)}(y) = \Psi(n,y) = \begin{cases} 0 & \quad 2n \leq y \leq 2n + n^2 \\ \uparrow & \quad \text{otherwise} \end{cases}$

Hence the domain of $W_n = \{2n, 2n + 1, ..., 2n + n^2\}$.

William
  • 19,935
  • Why did you post this answer given that the OP already had edited his question to include that exact answer? (Just curious.) – Quinn Culver May 03 '13 at 16:26
  • @QuinnCulver I read the first line to get the question and did not continue reading any further. It is surprising how similar they are. – William May 03 '13 at 20:30