Can any finite digit of the non-computable function always be a computable?

70 Views Asked by At

Can any finite digit of the non-computable function always be computable? If so, does this create a contradiction?

Let $\left\{a_n\right\}$ be a non-computable binary sequence and $f:\mathbb{N^+}\longrightarrow \left\{0,1\right\}$ be a $n'$th digit of the sequence $a_n$ or $f(n):=\left\{a_n\right\}_{n\in\mathbb{N^+}}$. Of course, we have no $n'$th digit formula for $f(n)$. Does this imply, any finite digit of the non-computable binary sequence is also not computable ? Otherwise, for any $n\in\mathbb N^+$, if $f(n)$ is computable, this implies $f(n)$ is computable which gives a contradiction. What are the points I miss?

2

There are 2 best solutions below

5
On BEST ANSWER

If I correctly understand your question, each individual digit of your sequence $f$ is 0 or 1. 0 is computable, namely by the program "print 0" (which ignores it input). Similarly, 1 is computable. So each individual digit in your sequence is computable. None of these trivial facts has any bearing on whether the whole function $f$ is computable.

6
On

Hint: A function $\ g:\mathbb{N}^+\rightarrow\{0,1\}\ $ is computable if there exists a Turing machine or equivalent that will eventually return the value of $\ g(n)\ $ when given the value of $\ n\ $ as input. Suppose $\ h:\mathbb{N}^+\rightarrow\{0,1\}\ $ is non-computable and $\ g:\mathbb{N}^+\rightarrow\{0,1\}\ $ is computable. Define $$ a_n=f(n)=\cases{g(n)& if $\ n\in\mathbb{N}^+\ $ is odd,\\ h\left(\frac{n}{2}\right)& if $\ n\in\mathbb{N}^+\ $ is even.} $$ Is $\ \left\{a_n\right\}\ $ computable or non-computable?