# Is function with finite amount of $\Phi_x(x+1)$ occurrences Turing computable?

I'm studying for my exam from Logic and Computability and we have to face following kind of examples:

$$f(x) = \begin{cases} \ 1 &\text{if }\Phi_x(x+1)\!\downarrow\text{ and }x\leq50\\ \ 0 &\text{otherwise.} \end{cases}$$

Unfortunatelly I'm not really clear on how to tackle those. $\Phi_x$ is the $x$-th computable function, thus it's also Turing computable. This implies, there exists a TM (we have $N$ of them) which halts and returns the output.

The task is to determine whether it's computable. In order to prove it we either provide an informal algorithm to show it's computable or a formal proof that it's not. Can any of you solve this example?

If $f(x)$ is computable, then $\Phi_x$ needs to halt for every $x \in\{1, \dots, 51\}$. However $\Phi_x$ could be undefined on one of the elements from $\{1, \dots, 51\}$ and keep looping forever.

At the other hand, there is an upper bound on $x$, which indicates its computability.

Please, can you show me the right direction?

Thanks!

• Let $S = \{ x \vert f(x) = 1 \}$. What are the possible values of $|S|$? – quicksort Jan 22 '17 at 1:48
• The set of all values at which the f(x) halts. Then the same set can be expressed as S = { x | phi(x) Halts }. Therefore there exists a computable function which can enumerate such a set S, thus the f is computable. Is this argumentation completely off? – TechCrap Jan 22 '17 at 11:43
• Before you consider the computability aspects, you need to read the question more carefully. $\Phi_x$ does not need to halt for every $x\in\{1, \dots, 51\}$. $\Phi_x$ only needs to halt for input $x+1$; i.e., you only need $\Phi_1(2), \Phi_2(3), \dots, \Phi_{50}(51)$ to halt (and $\Phi_0(1)$ if you can have $x=0$. Also, you say "there exists a TM (we have $N$ of them)" -- what's $N$? There are infinitely many Turing machines. – David Richerby Jan 22 '17 at 11:52
• @SimeonKredatus No, the set $S$ is the set of values $x$ for which $f(x)=1$: that's how it was defined. You need to read definitions more carefully. – David Richerby Jan 22 '17 at 11:54
• Rule of thumb: Functions of the form "if TM with ... does not halt, output x" are probably not computable. Except if they are. – Raphael Jan 22 '17 at 12:09

You can compute this function using a table of size 51. More generally, if $f$ is a function which differs from a computable function $g$ on a finite number of inputs, then $f$ is computable as well. In our case, $g$ is the constant zero function, which is trivially computable.