Skip to main content
2 of 2
added 72 characters in body

I know this is kind of a trivial answer but I think it's relevant if I understood you.

Ultimately (understanding computability as a property of sets of integers), whether or not a set of rationals is computable depends on how I choose to code them. For instance if I decide to code n/m by the pair (f(n), f(m)) rather than (n,m) where $f(2n)$ is the $n$-th element in $0'$ and $f(2n+1)$ is the $n$-th element not in $0'$ then all the sudden the set of rationals of the form $\frac{1}{o}$ with $o$ odd becomes non-computable.

Now this is a silly example because there is no good reason to use this coding. However, there are examples (representations of measures comes to mind but I'm sure there are better ones) where there are different codings we want to use for different purposes. So there just isn't a fact of the matter as to whether the set of rationals I gave above is computable...it is on one coding and not on another. So I don't see how what you are asking for could possibly work.

It's just that we usually gloss over the fact that the choice of coding also matter because the Church-Turing thesis tells us that in normal circumstances any way we might be inclined to regard as an algorithmic manipulation will correspond to a computable operation if we choose a coding that we also regard as algorithmic (i.e. something humans can do with pen and paper). But that's a contingent philosophical thesis not a mathematically formalizeable claim.

But I worry I'm misunderstanding you and didn't give a good response.

EDIT: I was misunderstanding the question...see the comments below.