As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring?

Conditions on either field or subring are fine.

  • 2
    $\begingroup$ This question might be better suited for mathoverflow.net, but either way, you need to make it more specific. There is no sensible nontrivial answer at this level of generality. $\endgroup$ Aug 29 '14 at 12:16
  • $\begingroup$ No need to close, this could go to Mathoverflow or here. $\endgroup$ Aug 29 '14 at 20:31
  • $\begingroup$ Specifically, three people think that this question deserves closing because it is "too broad". But it is not. It is very specific, except that most people won't know how to formulate the concepts involved, in particular it would be helpful to explain what a "computable" ring is. $\endgroup$ Aug 29 '14 at 20:32
  • 1
    $\begingroup$ @Andrej, you seem to be able to understand what the OP is looking for but the question still seems unclear and too broad to me in its current form even after reading your comments and answer. Your answer is as usual very interesting to read but I can't even tell if your answer is what the OP is looking for. The question clearly needs clarification to make others also able to understand what the OP is looking for. $\endgroup$
    – Kaveh
    Aug 30 '14 at 5:26
  • 1
    $\begingroup$ In these sorts of questions I find that the OP often does not really know what it means for a structure to be computable (present company excluded, of course). I think part of the problem is that people know too little about computability on mathematical structure to be even able to ask the question. For instance, this question seems to ask what might be some algebraic conditions on a ring to make it computable. The answer is: without further restrictions (such as "equality must be decidable") every ring can be equipped with a computable structure, albeit the trivial one. $\endgroup$ Aug 30 '14 at 8:21

The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper "Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions". There we give general conditions on what it means for a substructure of an algebraic structure to be computable. Let me give a summary, but I recommend reading the paper for thorough understanding.

We work with respect to an arbitrary model of computation, such as Turing machines, Type II Turing machines, topological models, $\lambda$-calculus, a programming language, etc. The formalism which encompasses all of these is realizability theory.

There is an embedding $\nabla : \mathsf{Set} \to \mathsf{Asm}$ from the category of sets to the category of assemblies (over some partial combinatory algebra, see our paper). The category of assemblies can be thought of as a category of sets equipped with a computability structure. The embedding $\nabla$ maps sets to sets equipped with trivial computability structure, namely, if $S$ is a set then $\nabla S$ is the set $S$ in which every $x \in S$ is realized by every realizer (if you've never heard of realizability before, think of Gödel encodings of objects). Intuitively this says that when we look at a realizer we have absolutely no idea which element it represents.

Assume a fixed signature $\Sigma$ for an algebraic structure (such as one of a ring) and let $\mathcal{A}$ be a $\Sigma$-algebra in the category of sets, i.e., what people normally think of when they say $\Sigma$-algebra. Because $\nabla$ preserves products, it maps $\mathcal{A}$ to a $\Sigma$-algebra $\nabla \mathcal{A}$ in $\mathsf{Asm}$. Now, a computable $\Sigma$-subalgebra of $\mathcal{A}$ is just a subalgebra of $\nabla \mathcal{A}$ in the category $\mathsf{Asm}$.

When we unravel what this means in terms of realizers we see that it is the expected thing: for $\mathcal{B}$ to be a computable subalgebra of $\mathcal{A}$ it has to be a subalgebra in the usual sense (of course), you have to give a realizability relation for the carrier of $\mathcal{B}$ which explains how the elements of carrier are realized, and all the operations on $\mathcal{B}$ must be realized (computable) with respect to the chosen realizability relation on the carrier.

It occurs to me that maybe you are asking the following question: given a subalgebra $\mathcal{B}$ of an algebra $\mathcal{A}$ is there some computable structure on $\mathcal{B}$, i.e., is there some way of making all the operations on $\mathcal{B}$ computable? First note that $\mathcal{A}$ does not play a role here. Second, if the only requirement is that the operations on $\mathcal{B}$ be computable, then the answer is always "yes, just use the trivial computability structure $\nabla \mathcal{B}$". That is, represent every element of $\mathcal{B}$ with any realizer you want, say 42, and then all operations are implemented by functions that always return 42. In order to avoid such a silly answer you have to impose further conditions -- and that's what our paper is about.


Not the answer you're looking for? Browse other questions tagged or ask your own question.