Mapping natural numbers to rationals

80 Views Asked by At

I'm prepping for an exam, and I came across this:

$$x_K = \sum_{n\in K} 2^{-n}$$

(K is the Halting problem)

Does there exist a computable function $f_x$ : N$\mapsto$Q where these conditions are satisfied?

(i) For all m$\in$N, 0$\leqq$f(t)

(ii) $\lim_{t\to \infty}$ = $x_k$

1

There are 1 best solutions below

0
On

It's possible that you meant to ask whether there is a computable function $f:\mathbb N\to\mathbb Q$, taking non-negative values, such that $\lim_{k\to\infty}f(k)=x_K$. (Although this question is rather far from what you wrote, it's the closest thing I can think of that makes sense.) If so, the answer is yes. Fix an algorithm enumerating $K$, and define $f(k)$ to be the sum of $2^{-n}$ over all those (finitely many) $n$ such that your fixed algorithm has enumerated $n$ as a member of $K$ within the first $k$ computation steps.