Non-computable functions by summing computable functions

118 Views Asked by At

The problem is to show that you may get a non-computable (non-recursive) function if you sum up an infinite number of computable (recursive) functions.

$$g(x) = \sum_{i=0}^\infty f(x, i)$$

show that $g(x)$ is non recursive, where $f(X, i)$ is recursive.

Can I use

$$g(x) = \sum_{i=0}^\infty 2^f,$$

where $f(i)$ is the Busy Beaver function?

And why can't I just use something like this: let infinite number of $f(x, i)$ equal $1$, so the sum will be divergent, which means its not computable.

1

There are 1 best solutions below

2
On

Let $A$ be a non-recursive set. Let $f(x,i)$ be $1$ if $x=i\in A$ and $0$ in all other cases. So, for each fixed $i$, $f(X,i)$ is the characteristic function of the singleton $\{i\}$ if $i\in A$ and the identically zero function if $i\notin A$. In either case, it's recursive. But the sum over all $i$ is the characteristic function of $A$, which isn't recursive.