By computable real I mean $x\in\mathbb{R}$ such that there is some computable total function $p_x$ that takes a natural number $n$ and returns a dyadic rational $r$ such that $|x-r|<2^{-n}$. I think this is probably equivalent to any other reasonable definition but I want to fix this to avoid ambiguity.

By a semi-decidable set $S$ of computable reals, I mean that there should be a program that, when given the Godel code for some $p_x$, halts exactly when $x\in S$.

One easy class of examples of semi-decidable sets of reals is given by open intervals $(a,b)$ where $a$ and $b$ are both computable.

Is it true that every semi-decidable set is open?

I think this should be true, essentially because if a computable process $P$ takes $p_x$ and then decides that $x\in S$, it must have done so using at most finitely many calls to $p_x$. But how do I know that $P$ did not do something sneaky by looking at the code for $p_x$? This should be impossible, but e.g. Rice's theorem does no apply directly because I am not assuming that $P$ decides some property of arbitrary programs, just those that happen to represent computable reals (and note that these are not even a r.e. set).

  • $\begingroup$ Following this answer, it is enough to find a computable sequence $x_i$ such that $x_i\notin S$ but $\lim x_i$ is computable and in $s$. If $S$ is not open, by definition (almost) there exists a Cauchy sequence $x_i$ which lies outside of $S$ and converges to a boundary point of $S$. The problem is making the sequence constructive somehow, in order to apply a reduction from the complement of the halting problem. $\endgroup$ – Ariel Nov 12 '18 at 13:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.