# Computability of the function $P(x)=\varphi_x(x)$ [closed]

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.

## 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.

• 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. – Raphael Nov 8 '13 at 11:47

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.