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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.