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!

Improve this question
$\endgroup$
7
  • $\begingroup$ Let $S = \{ x \vert f(x) = 1 \}$. What are the possible values of $|S|$? $\endgroup$
    – quicksort
    Jan 22, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 12:09

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\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, 2017 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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