3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Let $S = \{ x \vert f(x) = 1 \}$. What are the possible values of $|S|$? $\endgroup$ – quicksort Jan 22 '17 at 1:48
  • $\begingroup$ 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? $\endgroup$ – TechCrap Jan 22 '17 at 11:43
  • $\begingroup$ 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. $\endgroup$ – David Richerby Jan 22 '17 at 11:52
  • $\begingroup$ @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. $\endgroup$ – David Richerby Jan 22 '17 at 11:54
  • 1
    $\begingroup$ Rule of thumb: Functions of the form "if TM with ... does not halt, output x" are probably not computable. Except if they are. $\endgroup$ – Raphael Jan 22 '17 at 12:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note bene: we don't know the content of this table. But we know one of all the tables of this size is the right one, which is quite enough. $\endgroup$ – Raphael Jan 22 '17 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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