<p>The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper <a href="http://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of">"Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions"</a>. 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.</p>

<p>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 <em>realizability theory</em>.</p>

<p>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.</p>

<p>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}$.</p>

<p>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.</p>

<p>It occurs to me that maybe you are asking the following question: <em>given</em> a subalgebra $\mathcal{B}$ of an algebra $\mathcal{A}$ is there <em>some</em> 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 <em>only</em> 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.</p>

CC BY-SA 3.0
2014-08-29T20:21:46.950Z
2014-08-29T20:35:34.487Z
2014-08-29T20:35:34.487Z
Andrej Bauer
<p>As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring?</p>

<p>Conditions on either field or subring are fine.</p>

CC BY-SA 3.0
2014-08-29T12:16:22.247Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-08-29T20:31:01.127Z
No need to close, this could go to Mathoverflow or here.
Andrej Bauer
CC BY-SA 3.0
2014-08-29T20:32:17.473Z
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.
Andrej Bauer
CC BY-SA 3.0
2014-08-30T05:26:35.557Z
@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.
Kaveh
CC BY-SA 3.0
2014-08-30T05:33:35.110Z
E.g. the OP can explain why they are interested in the question.
Kaveh
CC BY-SA 3.0
2014-08-30T08:21:56.923Z
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.
Andrej Bauer
CC BY-SA 3.0
2014-08-31T19:58:27.890Z
I don’t understand what is going on with all this category theory, but under the standard definition of a computable structure from computability theory, it’s most certainly *not* true that every ring (even countable) is computable.
Emil Jeřábek
<computability><algebra><comp-number-theory>
What is necessary and/or sufficient requirement for a subring of a field to be computable?
Korpam
# What is necessary and/or sufficient requirement for a subring of a field to be computable?

(Asked by: username_0 on 2014-08-29)

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.

**Tags:** computability, algebra, comp-number-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: No need to close, this could go to Mathoverflow or here.  
> **username_2**: 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.  
> **username_3**: @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.  
> **username_3**: E.g. the OP can explain why they are interested in the question.  
> **username_2**: 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.  
> **username_1**: I don’t understand what is going on with all this category theory, but under the standard definition of a computable structure from computability theory, it’s most certainly *not* true that every ring (even countable) is computable.  

---

## 1 answers

### Answer by username_2 on 2014-08-29. Score: 5

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"](http://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of). 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.


---

