-2

Is the following computable ?

Notation: We use $Φ_k$ to denote the k-th computable function

$$g(x) = \begin{cases} 1 & ∀z (Φ_x(z) = 2 ∨ Φ_x(z) ↑) \\ ↑\ &otherwise \end{cases} $$

I really need your help.

Thanks

Carl Mummert
  • 81,604
Norman
  • 45
  • When you write $\Phi x$ do you mean what is usually notated $\varphi_x$, that is, the $x$th partial recursive function in some fixed enumeration? And what's the meaning of the $\ge 0$ applied to a logical formula? – hmakholm left over Monica Jan 07 '18 at 14:10
  • Thank you for the answer. > 0 was my mistake sorry i edited. – Norman Jan 07 '18 at 14:14
  • 1
    This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. In particular, what do you already know about computability, and what examples of noncomputable functions do you know? – Carl Mummert Jan 07 '18 at 14:34
  • This is what Rice's Theorem is about. – MJD Jan 07 '18 at 14:38
  • 2
    @MJD: there is at least something interesting in this problem: if we switch the $1$ and $\uparrow$ return value, the resulting function is partial computable. Because $g$ can be partial, Rice's theorem is not directly applicable. – Carl Mummert Jan 07 '18 at 14:46
  • As Carl said, you need to add more context. In particular, do you have a guess what the answer is? (For example, do you think you could figure out, in a finite amount of time, what $g(17)$ should be?) – Noah Schweber Jan 07 '18 at 15:09

1 Answers1

1

No it's not. By contradiction, suppose that g is computable, then so is $$ P\langle x,y\rangle=g(x) $$ By fixed point theorem, there is a $n$ such that $\Phi_n(y)$ computes $P\langle n,y\rangle$

Not that $\forall y \Phi_n(y)=1$ or $\forall y \Phi_n(y)\uparrow$ by definition (because it's always equal to $g(n)$)

But $\Phi_n(y)=P\langle n,y\rangle=g(n)=1$ iff $\Phi_n(y)\uparrow$

And $\Phi_n(y)=P\langle n,y\rangle=g(n)\uparrow$ iff $\Phi_n(y)=1$

This is a contradiction, hence $g$ is not computable.

Xoff
  • 10,310