3

I know that there exist functions such that no computer program can, given arbitrary input, produce the correct function value. There is nothing, however which would prohibit us from knowing the function value for certain specific inputs.

Suppose we have an uncomputable function $f$ defined on N and an infinite sequence of programs $p_1,p_2,p_3,..$ such that $p_n$ computes $f(n)$ no matter what it is given as input.

Since we could use this infinite sequence of programs to compute the function value for an arbitrary input, I am led to believe this sequence of programs cannot exist.

Thus, for any uncomputable function there must exist a particular element in the domain of the function such that its function value cannot ever be computed.

Is my reasoning valid?

Adam
  • 3,422
  • 1
  • 33
  • 50
  • The fact that there is a No answer and a Yes answer is that for a specific $n$, No, $f(n)$ can always be computed (because it's just an integer), but Yes, $f(n)$ can't be decided (you can't prove $f(n)=m$). I really think that your question is about decidability, that's why I answered "Yes". – Xoff Dec 30 '13 at 14:16

3 Answers3

4

No. For example, there are uncomputable functions taking values in $\{0,1\}$ (which might e.g. represent "no" and "yes"). Each program $p_n$ is very simple, in fact each is one of two possible programs: one that just prints "$0$", another that just prints "$1$". The sequence $p_n$ certainly exists, we just don't happen to know it, i.e. for some $n$ we don't know whether the answer is $0$ or $1$.

Robert Israel
  • 448,999
3

Yes, you're right !

The main problem of uncomputable function is that at some point (for a specific $n$), we can't compute it.

Obviously, if we could, for each $n$, find the right program $p_n$ that computes $f(n)$, then $f$ would be computable. As Robert Israel mentioned, it does not prevent $p_n$ from existing. We just don't know how to find it.

Note that the "we can't compute it for that particular $n$" is related to the underlying mathematical theory you use to do your computation. It means that there is no proof that $p_n$ is the right program for $f(n)$. But uncomputability is still uncomputabillity, so if you manage to prove that $p_n$ is indeed the program that computes $f(n)$ for that particular $n$ in a particular (recursive) theory $T$, be sure there is some other $m>n$ such that you won't be able to find $p_m$ using $T$.

Xoff
  • 10,310
1

Suppose $f : \mathbb{N}\to\mathbb{N}$. Programs that compute constant functions on natural numbers always exist. Therefore for any function $f : \mathbb{N} \to \mathbb{N}$ there "exists" a sequence of programs $\{p_n\}$ such that $p_n$ computes $f(n)$ for any given input.

Now one has to be a bit careful when saying "exists". This depends on your metatheory. In ordinary mathematics with classical logic this sequence "exists", but the catch is that in general there will not be a Turing machine that would enumerate it. If your metatheory is weaker, then you perhaps won't be able to construct such a sequence of programs at all.

So there is no uniform way to compute $f$, i.e. a finite sequence of instructions that would compute $f(n)$ for any $n$, but for each particular $n$, this always exists, since the value of $f$ is some fixed natural number.

Aleš Bizjak
  • 2,691