-2
$\begingroup$

Let $P$ be the predicate on natural numbers defined by $P(x) \iff \varphi_x(x) = 1$ where $\varphi_x$ is the $x$-th computable function. Show that $P$ is not computable.

$\endgroup$

closed as unclear what you're asking by D.W., Luke Mathieson, Raphael Nov 8 '13 at 11:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This is a homework dump, not a question. If you have a specific question regarding the phrasing of the problem or a step in your solution attempts, please edit the question and we can reopen. $\endgroup$ – Raphael Nov 8 '13 at 11:47
2
$\begingroup$

This is the standard argument by diagonalization. Let the $x$-th computable map be $\varphi_x$.

Suppose $P$ were computable, which by definition means that the following function $p$ is computable: $p(x) = (\mathsf{if}\ \varphi_x(x) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0)$. Therefore the function $f(x) = 1 - p(x)$ is computable also. There is a number $y$ such that $\varphi_y = f$. Either $p(y) = 0$ or $p(y) = 1$:

  • if $p(y) = 0$ then $$0 = p(y) = \\ (\mathsf{if}\ \varphi_y(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - p(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - 0 = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ \mathsf{true} \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = 1,$$ a contradiction.

  • similarly, if $p(y) = 1$ then $$1 = p(y) = \\ (\mathsf{if}\ \varphi_y(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - p(y) = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ 1 - 1 = 1 \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = \\ (\mathsf{if}\ \mathsf{false} \ \mathsf{then}\ 1 \ \mathsf{else}\ 0) = 1,$$ a contradiction.

We have reached a contradiction, so our initial assumption that $P$ is computable is fasle.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.