0

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$

Heplar
  • 41
  • You need to clean up your indices quite a bit here. As it stands, it's immensely confusing what you're trying to ask, and the question title is no help... – Steven Stadnicki Nov 15 '13 at 02:11

1 Answers1

0

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.

Andreas Blass
  • 71,833