<p>This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.</p>

<p>There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact <a href="https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf" rel="noreferrer">Turing's original paper on Turing machines</a> starts with the following sentence:</p>

<blockquote>
  <p><em>The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.</em></p>
</blockquote>

<p>Sometimes it pays to go back to the source.</p>

<p>There are several ways to set up computability on general sets, of which one of the most general ones is <a href="https://ncatlab.org/nlab/show/realizability" rel="noreferrer">realizability theory</a>. The idea of realizability theory goes back to Kleene's paper <a href="http://www.jstor.org/stable/2269016" rel="noreferrer">On the Interpretation of Intuitionistic Number Theory</a> from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).</p>

<p>Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the <span class="math-container">$\lambda$</span>-calculus, a programming language, or any other <a href="https://ncatlab.org/nlab/show/partial+combinatory+algebra" rel="noreferrer">partial combinatory algebra</a> (you can even take certain topological spaces to be "models of computation", this stuff is <em>general</em>). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should <em>not</em> assume that the use of <span class="math-container">$\mathbb{N}$</span> is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped <span class="math-container">$\lambda$</span>-calculus, certain categories of games, etc.)</p>

<p>A computability structure on a set <span class="math-container">$X$</span> is given by a relation <span class="math-container">$\Vdash_X$</span> between <span class="math-container">$\mathbb{N}$</span> and <span class="math-container">$X$</span>, called the <em>realizability relation</em>, such that for every <span class="math-container">$x \in X$</span> there <span class="math-container">$n \in \mathbb{N}$</span> such that <span class="math-container">$n \Vdash_X x$</span>. We call such structures <em>assemblies</em>. This definition directly corresponds to the intuitive idea that some piece of data <span class="math-container">$n$</span> respresents, or <em>realizes</em>, an element <span class="math-container">$x \in X$</span>. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)</p>

<p>Given two assemblies <span class="math-container">$(X, {\Vdash_X})$</span> and <span class="math-container">$(Y, {\Vdash_Y})$</span>, a map <span class="math-container">$f : X \to Y$</span> is <em>realized</em> (or "computable") if there is a Turing machine <span class="math-container">$T$</span>, such that, whenever <span class="math-container">$n \Vdash_X x$</span> then <span class="math-container">$T(n)$</span> terminates and <span class="math-container">$T(n) \Vdash_Y f(x)$</span>. Again, this is a direct transliteration of what it means informally to "program" an abstract function <span class="math-container">$f$</span>: the corresponding Turing machine does to representing data whatever <span class="math-container">$f$</span> does to the corresponding elements.</p>

<p>Assemblies may be extended to a <a href="https://ncatlab.org/nlab/show/realizability+topos" rel="noreferrer">realizability topos</a>. A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.</p>

<p>Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's <em>function realizability</em>, and goes under the name of <a href="https://eccc.weizmann.ac.il/resources/pdf/ica.pdf" rel="noreferrer">computable analysis</a>.</p>

<p>Let me comment on the "coordinate free" requirement:</p>

<ul>
<li><p>Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.</p></li>
<li><p>A set <span class="math-container">$X$</span> may be equipped with <em>many</em> computability structures <span class="math-container">$\Vdash_X$</span>, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on <span class="math-container">$X$</span> are computably equivalent.</p></li>
<li><p>If we work concretely with computability structures <span class="math-container">$(X, {\Vdash_X})$</span>, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.</p></li>
<li><p>To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).</p></li>
<li><p>We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.</p></li>
</ul>

CC BY-SA 3.0
2017-12-03T18:33:27.030Z
I don't see the choice of $\mathbb{N}$ here as analogous to the choice of $\mathbb{R}$ as the field over which we might consider vector spaces.  Rather this notion of "realizability relation" seems to me like defining what it means to be measurable by defining the Borel measure on $\mathbb{R}$ and then declaring "a measurable space is anything that bijects with $\mathbb{R}$ and a measurable function is anything which induces a measurable map $\mathbb{R} \to \mathbb{R}$.
Tom Ellis
CC BY-SA 3.0
2017-12-03T18:38:08.627Z
Measurable spaces arise naturally out of (some) topological spaces and it's generally considered a *theorem* that the non-discrete ones are measurably isomorphic to $\mathbb{R}$.  What I'd ideally like to find is the computation theory analogue of the former construction.  What's the underlying structure that gives rise to something you can compute on?  A correspondence with $\mathbb{N}$, imposed by fiat, isn't particularly satisfying.
Tom Ellis
CC BY-SA 3.0
2017-12-03T18:40:40.740Z
There is no "choice of $\mathbb{N}$", there is only choice of a model of computation. If by "choice of $\mathbb{N}$" you mean "let us use Turing machines (coded by numbers)", then my point is this: for each choice of computability structure $\mathbb{S}$ you get a realizability topos $\mathrm{RT}(\mathbb{S})$. This is analogous to: for each choice of a field $F$ you get the category $\mathrm{Vect}_F$ of vector spaces over $F$.
Andrej Bauer
CC BY-SA 3.0
2017-12-03T18:41:23.520Z
Imposing measures on sets is indeed a bit like imposing computability structures on sets. And in both cases some sets have natural structures associated with them.
Andrej Bauer
CC BY-SA 3.0
2017-12-03T18:42:46.077Z
Ah, perhaps there's something else here that needs to be clarified: first we choose a computability model $\mathbb{S}$, and we fix it. Then we consider computability structures $\Vdash_X$ for this fixed $\mathbb{S}$. We don't change it (just like we don't change the field over which we form vector spaces).
Andrej Bauer
CC BY-SA 3.0
2017-12-03T19:01:50.737Z
That's all very well, but the construction you presented still feels like saying "a vector space over $F$ is anything that bijects with $F^n$" rather than giving an axiomatic definition.
Tom Ellis
CC BY-SA 3.0
2017-12-03T19:12:05.540Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/69663/discussion-between-tom-ellis-and-andrej-bauer).
Tom Ellis
CC BY-SA 3.0
2017-12-03T22:03:56.187Z
Sorry, but I am not interested in some vague and pointless analogy between realizability and vector spaces. You asked a non-research-level question on a research forum, to which I obliged by explaining a little bit about the topic (having studied the topic for 20 years). I am happy to help, but at this point I suggest that you actually consult some of the references I suggested, if you're serious about this question. I wish you a lot of success.
Andrej Bauer
CC BY-SA 3.0
2017-12-04T11:56:53.297Z
Dear Andrej, let me thank you for your considered responses.  I'm delighted that a 20 year veteran of the field would take time to enlighten a neophyte like myself rather than voting to close my question as pointless.  I'm also pleased to infer that topos theory and the pages on the nLab are now considered accessible to those at the pre-research level.
Tom Ellis
CC BY-SA 3.0
2017-12-04T11:56:58.173Z
Still, I must protest at the description of my analogy as "pointless".  It is, in fact, the whole point of the question.  The act of choosing a computability structure $\mathbb{S}$ was exactly what I was trying to avoid.  I don't see how working in a realizability topos overcomes this objection either, from what I can understand of the definition.  Anyway, I must apologise for my clumsy presentation of what to me seems to be a deep philosophical, and perhaps unanswered, question as something rather trivial and uninteresting.
Tom Ellis
CC BY-SA 3.0
2017-12-04T18:11:05.630Z
At the end of my answer I hinted how you can avoid choosing a computability structure: work in constructive logic, so that everything you do is computable (in any computability structure).
Andrej Bauer
CC BY-SA 4.0
2019-06-09T09:10:59.180Z
@TomEllis Your choice of computability structure is restricted if your set has some special structure. For example, on natural numbers, you want your computability structure such that addition and multiplication (and other stuff) are realized. This restricts your choice, and I'd expect the usual computability structure on natural numbers to be definable by something like: the smallest such that <some well chosent set of functions> are computable. | Also, when your set has some special structure, you want your $g$ to be an isomorphism.
xavierm02
CC BY-SA 4.0
2019-06-09T09:15:17.820Z
@TomEllis And about axiomatization: it's the same as the one of the structure that your set has, except that all functions that appear in this axiomatizaton should be computable. Just like when you axiomatize topological groups, you ask that all operations (multiplication and inverse) are continuous, when you axiomatize computable groups, you ask that all operations are computable.
xavierm02
CC BY-SA 4.0
2017-12-03T17:59:16.987Z
2019-06-09T06:34:01.577Z
2019-06-09T06:34:01.577Z
Andrej Bauer
<p>The two papers below develop a notion of computability for arbitrary sets.
Interestingly even a notion of complexity theory can be defined for this model of computation.  </p>

<p><a href="http://users.math.cas.cz/~thapen/CRSF_APAL.pdf" rel="nofollow noreferrer">Cobham Recursive Set Functions and Weak Set Theories
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.</a> </p>

<p><a href="http://users.math.cas.cz/~thapen/papertwo_revision.pdf" rel="nofollow noreferrer">Subset-Bounded Recursion and a Circuit Model for Cobham Recursive Set Functions 
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen. </a></p>

CC BY-SA 3.0
2017-12-01T17:48:04.567Z
2017-12-01T17:48:04.567Z
Mateus de Oliveira Oliveira
<p>There is a concept of complexity and computation over the reals. A textbook I would direct you to is: <a href="https://rads.stackoverflow.com/amzn/click/0387982817" rel="nofollow noreferrer">https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817</a></p>

<p>I know of one lab that studies this specifically: <a href="https://complexity.kaist.ac.kr/" rel="nofollow noreferrer">https://complexity.kaist.ac.kr/</a></p>

CC BY-SA 3.0
2017-12-03T17:23:37.007Z
That one is not particularly realistic as it implies that the Halting oracle is computable.
Andrej Bauer
CC BY-SA 3.0
2017-12-02T12:12:12.710Z
2017-12-02T12:12:12.710Z
MRC
<p>This is similar to how we define computability in terms of Turing machines and then promptly forget about Turing machines.  Since it turns out a Turing machine is as good a definition as any other, we use it as an anchor for an entire equivalence class of models, and we end up with the same class no matter which element we generate it from. Basically this is the Church-Turing thesis and it defines the set of computable bit strings.</p>

<p>Similarly, to define computability on a different set $S$, we anchor it with a particular partial function from bit strings to $S$.  Actually it does not matter if this function is a bijection or an injection or any other type of function (for a case where we don't really want it to be an injection, consider a group defined by its presentation where we don't have a unique representation for its elements).  It doesn't even have to be a surjection if we permit that singleton sets can be uncomputable. By composing this function with any computable bijection from bit strings to bit strings (a concept already defined), we get a definition of computability for $S$ that's invariant with respect to the function we originally picked (as long as we picked something reasonable).  That is, a CT thesis for our set $S$.  But if we don't pick a reasonable function, we get a different definition of computability.</p>

<p>This function also serves to define the computability of other functions with domain or range equal to $S$. By changing the range to $S$, keeping the domain as $\{0,1\}^*$, we also get an $O(1)$-invariant definition of Kolmogorov complexity for $S$.  And we can finally say that the function we have chosen is itself computable.</p>

<p>So I think the answer to your question is NO. We have to define computability for each set that we want to talk about, because there are non-equivalent definitions. Aside from a very technical or pedagogical discussion it shouldn't be necessary, since a reasonable person can imagine a reasonable definition independently.</p>

<p>But wait, let $S$ be a countably infinite set, and that's it. What's our reasonable definition of computability for $S$? Knowing that the set of bijections between $S$ and $\{0,1\}^*$ is non-empty doesn't tell us which are reasonable. We're out of luck without more details.</p>

<p>And we may encounter multiple inequivalent but equally-reasonable alternatives.  Suppose every tree has some number of red leaves and some number of green leaves, and that for every $r \in \mathbb{N}$ there exists exactly one tree with $r$ red leaves, and that for every $g \in \mathbb{N}$ there exists exactly one tree with $g$ green leaves. Both bijections are reasonable in the sense that we can count the leaves and distinguish the colors, and we can walk aimlessly around the woods counting leaves on trees until we find the tree with exactly $23$ green leaves, or the one with $23$ red leaves. It's not clear whether to identify a tree using  its red leaf count or its green leaf count because this choice leads to inequivalent definitions of computability for sets of trees.  If we instead make our definition by combining the counts with a computable pairing function bijective from $\mathbb{N}^2$ to $\mathbb{N}$ (having appropriately defined computability on $\mathbb{N}^2$), that also uniquely identifies each tree, but the situation is even worse because this is not a bijection between trees and $\mathbb{N}$, now maybe all computable sets of trees are finite!</p>

<p>So in order to avoid the entire discussion it should be understood not only that there exists a reasonable definition of computability on the set in question, but also that there is exactly one class of reasonable definitions.</p>

<p>I think the situation becomes a lot more interesting if we bring time complexity into the picture. Even when just considering integers, our choices matter more. For example, what if we wanted to represent each number as a sum of four squares? We can find such a representation, starting from a base representation, in expected quadratic time with access to randomness. Or instead, as a list of its prime factors, which may or may not be possible to compute in polynomial time. To the extent that we allow hard representations, we lose precision in time complexity. For example, we can't meaningfully say that some function $F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time if we have a representation of $\mathbb{N}$ that might require more than quadratic time to convert to or from a base representation. I think this perspective reveals that base representation is a somewhat arbitrary standard.  (Standard in the sense that base representation is what anyone has in mind when they say something like "$F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time", if the underlying model is one that computes bit strings from bit strings and we're supposed to infer the meaning.)</p>

CC BY-SA 3.0
2017-12-01T17:40:38.133Z
2017-12-02T02:48:56.983Z
2017-12-02T02:48:56.983Z
Dan Brumleve
<p>Is there a notion of computability on sets other than the natural numbers?  For the sake of argument, let's say on sets <span class="math-container">$S$</span> that biject with <span class="math-container">$\mathbb{N}$</span>.</p>
<p>It's tempting to say &quot;yes, they are those functions of the form <span class="math-container">$g \circ f \circ g^{-1}$</span> where <span class="math-container">$g$</span> is any bijection <span class="math-container">$\mathbb{N} \to S$</span> and <span class="math-container">$f$</span> is any computable function <span class="math-container">$\mathbb{N} \to \mathbb{N}$</span>&quot;.  I'm cautious of this definition for two reasons.</p>
<ol>
<li><p>It privileges <span class="math-container">$\mathbb{N}$</span> over other countable sets.  Why is <span class="math-container">$\mathbb{N}$</span> special when it comes to defining computability?  I'd like a &quot;coordinate free&quot; definition of computability without reference to any privileged set in the same way I might like a &quot;coordinate free&quot; definition of a linear algebra concept without reference to any privileged basis.</p>
</li>
<li><p>It raises questions about the choice of <span class="math-container">$g$</span>.  I suspect it may be possible to find contradictions by particularly pathological choices of <span class="math-container">$S$</span> and <span class="math-container">$g$</span>.  For example if I choose <span class="math-container">$S = \mathbb{N}$</span> and <span class="math-container">$g$</span> some non-computable bijection is it really the case that <span class="math-container">$g \circ f \circ g^{-1}$</span> is computable for all computable <span class="math-container">$f$</span>?</p>
<p>It's tempting to require in the definition that <span class="math-container">$g$</span> be computable but unfortunately that's begging the question.</p>
</li>
</ol>
<p>Is there some general way of describing computability on countable sets other than <span class="math-container">$\mathbb{N}$</span>?</p>

CC BY-SA 3.0
2017-12-01T15:36:49.600Z
Well, aside from $\mathbb{N}$, computability is also often defined on $\Sigma^*$, where $\Sigma$ is a finite alphabet... But again, those definitions differ by a *computable* bijection $\mathbb{N} \to \Sigma^*$ (that is, in one direction it's computable using the $\mathbb{N}$ definition, and it's inverse is computable using the $\Sigma^*$ definition). So you definitely can do it, where your $g$ and $g^{-1}$ are both computable, but I agree that's begging the more general question...
Joshua Grochow
CC BY-SA 3.0
2017-12-01T17:58:23.817Z
What about model of computations like tiling systems, cellular automata, tag systems, and so on?
Marzio De Biasi
CC BY-SA 3.0
2017-12-02T14:29:46.450Z
Why should we not privilege $\mathbb{N}$ over other countable sets? We have an extremely strong reason to do so: CPUs, i.e. the thing that does computation, works on $\mathbb{N}$ (or finite strings over $\mathbb{B}$ which is essentially the same thing). Sure you can choose other sets, but why should anyone accept your definition? How do you justify any claim that what you call computability really is, except by relating it to computation on $\mathbb{N}$, i.e. CPUs?
Martin Berger
CC BY-SA 3.0
2017-12-02T16:37:26.740Z
@Martin, I give an argument in my answer that we privilege $\{0,1\}^*$ over $\mathbb{N}$ at least to a certain extent with regards to time complexity.  The reason this is wrong without some introspection is that we might assume certain results are natural when they're actually just artifacts of the model.
Dan Brumleve
CC BY-SA 3.0
2017-12-02T17:27:39.647Z
@DanBrumleve I agree that as soon as time-complexity is taken into account  $\mathbb{B}^*$ and $\mathbb{N}$ diverge, and $\mathbb{B}^*$ becomes the better model.  However OP's question was about *computability*, not complexity, and if mere computability is at stake $\mathbb{B}^*$ and $\mathbb{N}$ are essentially the same. We can always make things more difficult, e.g. why use standard asymptotic worst-case time complexity and not average case or fine-grained complexity etc.
Martin Berger
CC BY-SA 3.0
2017-12-03T18:03:54.633Z
Is there some reason you're limiting attention just to countable sets?
Andrej Bauer
CC BY-SA 3.0
2017-12-03T18:22:03.407Z
@AndrejBauer: Only to indicate that I'm interested in an answer even if it doesn't extend easily to larger sets.
Tom Ellis
CC BY-SA 3.0
2017-12-03T18:44:06.567Z
It extends to all sets (although once you go beyond the cardinality of continuum, it gets kind of funky).
Andrej Bauer
<computability>
Is there a notion of computability on sets other than the natural numbers?
Tom Ellis
# Is there a notion of computability on sets other than the natural numbers?

(Asked by: username_0 on 2017-12-01)

Is there a notion of computability on sets other than the natural numbers? For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.

It's tempting to say "yes, they are those functions of the form $g \circ f \circ g^{-1}$ where $g$ is any bijection $\mathbb{N} \to S$ and $f$ is any computable function $\mathbb{N} \to \mathbb{N}$". I'm cautious of this definition for two reasons.

1. It privileges $\mathbb{N}$ over other countable sets. Why is $\mathbb{N}$ special when it comes to defining computability? I'd like a "coordinate free" definition of computability without reference to any privileged set in the same way I might like a "coordinate free" definition of a linear algebra concept without reference to any privileged basis.
2. It raises questions about the choice of $g$. I suspect it may be possible to find contradictions by particularly pathological choices of $S$ and $g$. For example if I choose $S = \mathbb{N}$ and $g$ some non-computable bijection is it really the case that $g \circ f \circ g^{-1}$ is computable for all computable $f$?

   It's tempting to require in the definition that $g$ be computable but unfortunately that's begging the question.

Is there some general way of describing computability on countable sets other than $\mathbb{N}$?

**Tags:** computability
> **Comments:**
> **username_1**: Well, aside from $\mathbb{N}$, computability is also often defined on $\Sigma^*$, where $\Sigma$ is a finite alphabet... But again, those definitions differ by a *computable* bijection $\mathbb{N} \to \Sigma^*$ (that is, in one direction it's computable using the $\mathbb{N}$ definition, and it's inverse is computable using the $\Sigma^*$ definition). So you definitely can do it, where your $g$ and $g^{-1}$ are both computable, but I agree that's begging the more general question...  
> **username_2**: What about model of computations like tiling systems, cellular automata, tag systems, and so on?  
> **username_3**: Why should we not privilege $\mathbb{N}$ over other countable sets? We have an extremely strong reason to do so: CPUs, i.e. the thing that does computation, works on $\mathbb{N}$ (or finite strings over $\mathbb{B}$ which is essentially the same thing). Sure you can choose other sets, but why should anyone accept your definition? How do you justify any claim that what you call computability really is, except by relating it to computation on $\mathbb{N}$, i.e. CPUs?  
> **username_4**: @Martin, I give an argument in my answer that we privilege $\{0,1\}^*$ over $\mathbb{N}$ at least to a certain extent with regards to time complexity.  The reason this is wrong without some introspection is that we might assume certain results are natural when they're actually just artifacts of the model.  
> **username_3**: @DanBrumleve I agree that as soon as time-complexity is taken into account  $\mathbb{B}^*$ and $\mathbb{N}$ diverge, and $\mathbb{B}^*$ becomes the better model.  However OP's question was about *computability*, not complexity, and if mere computability is at stake $\mathbb{B}^*$ and $\mathbb{N}$ are essentially the same. We can always make things more difficult, e.g. why use standard asymptotic worst-case time complexity and not average case or fine-grained complexity etc.  
> **username_5**: Is there some reason you're limiting attention just to countable sets?  
> **username_0**: @AndrejBauer: Only to indicate that I'm interested in an answer even if it doesn't extend easily to larger sets.  
> **username_5**: It extends to all sets (although once you go beyond the cardinality of continuum, it gets kind of funky).  

---

## 4 answers

### Answer by username_5 on 2017-12-03. Score: 15

This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.

There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact [Turing's original paper on Turing machines](https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf) starts with the following sentence:

> *The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.*

Sometimes it pays to go back to the source.

There are several ways to set up computability on general sets, of which one of the most general ones is [realizability theory](https://ncatlab.org/nlab/show/realizability). The idea of realizability theory goes back to Kleene's paper [On the Interpretation of Intuitionistic Number Theory](http://www.jstor.org/stable/2269016) from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the $\lambda$-calculus, a programming language, or any other [partial combinatory algebra](https://ncatlab.org/nlab/show/partial+combinatory+algebra) (you can even take certain topological spaces to be "models of computation", this stuff is *general*). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should *not* assume that the use of $\mathbb{N}$ is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped $\lambda$-calculus, certain categories of games, etc.)

A computability structure on a set $X$ is given by a relation $\Vdash\_X$ between $\mathbb{N}$ and $X$, called the *realizability relation*, such that for every $x \in X$ there $n \in \mathbb{N}$ such that $n \Vdash\_X x$. We call such structures *assemblies*. This definition directly corresponds to the intuitive idea that some piece of data $n$ respresents, or *realizes*, an element $x \in X$. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)

Given two assemblies $(X, {\Vdash\_X})$ and $(Y, {\Vdash\_Y})$, a map $f : X \to Y$ is *realized* (or "computable") if there is a Turing machine $T$, such that, whenever $n \Vdash\_X x$ then $T(n)$ terminates and $T(n) \Vdash\_Y f(x)$. Again, this is a direct transliteration of what it means informally to "program" an abstract function $f$: the corresponding Turing machine does to representing data whatever $f$ does to the corresponding elements.

Assemblies may be extended to a [realizability topos](https://ncatlab.org/nlab/show/realizability+topos). A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.

Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's *function realizability*, and goes under the name of [computable analysis](https://eccc.weizmann.ac.il/resources/pdf/ica.pdf).

Let me comment on the "coordinate free" requirement:

* Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.
* A set $X$ may be equipped with *many* computability structures $\Vdash\_X$, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on $X$ are computably equivalent.
* If we work concretely with computability structures $(X, {\Vdash\_X})$, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.
* To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).
* We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.

> **Comments:**
> **username_0**: I don't see the choice of $\mathbb{N}$ here as analogous to the choice of $\mathbb{R}$ as the field over which we might consider vector spaces.  Rather this notion of "realizability relation" seems to me like defining what it means to be measurable by defining the Borel measure on $\mathbb{R}$ and then declaring "a measurable space is anything that bijects with $\mathbb{R}$ and a measurable function is anything which induces a measurable map $\mathbb{R} \to \mathbb{R}$.  
> **username_0**: Measurable spaces arise naturally out of (some) topological spaces and it's generally considered a *theorem* that the non-discrete ones are measurably isomorphic to $\mathbb{R}$.  What I'd ideally like to find is the computation theory analogue of the former construction.  What's the underlying structure that gives rise to something you can compute on?  A correspondence with $\mathbb{N}$, imposed by fiat, isn't particularly satisfying.  
> **username_5**: There is no "choice of $\mathbb{N}$", there is only choice of a model of computation. If by "choice of $\mathbb{N}$" you mean "let us use Turing machines (coded by numbers)", then my point is this: for each choice of computability structure $\mathbb{S}$ you get a realizability topos $\mathrm{RT}(\mathbb{S})$. This is analogous to: for each choice of a field $F$ you get the category $\mathrm{Vect}_F$ of vector spaces over $F$.  
> **username_5**: Imposing measures on sets is indeed a bit like imposing computability structures on sets. And in both cases some sets have natural structures associated with them.  
> **username_5**: Ah, perhaps there's something else here that needs to be clarified: first we choose a computability model $\mathbb{S}$, and we fix it. Then we consider computability structures $\Vdash_X$ for this fixed $\mathbb{S}$. We don't change it (just like we don't change the field over which we form vector spaces).  
> **username_0**: That's all very well, but the construction you presented still feels like saying "a vector space over $F$ is anything that bijects with $F^n$" rather than giving an axiomatic definition.  
> **username_0**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/69663/discussion-between-tom-ellis-and-andrej-bauer).  
> **username_5**: Sorry, but I am not interested in some vague and pointless analogy between realizability and vector spaces. You asked a non-research-level question on a research forum, to which I obliged by explaining a little bit about the topic (having studied the topic for 20 years). I am happy to help, but at this point I suggest that you actually consult some of the references I suggested, if you're serious about this question. I wish you a lot of success.  
> **username_0**: Dear Andrej, let me thank you for your considered responses.  I'm delighted that a 20 year veteran of the field would take time to enlighten a neophyte like myself rather than voting to close my question as pointless.  I'm also pleased to infer that topos theory and the pages on the nLab are now considered accessible to those at the pre-research level.  
> **username_0**: Still, I must protest at the description of my analogy as "pointless".  It is, in fact, the whole point of the question.  The act of choosing a computability structure $\mathbb{S}$ was exactly what I was trying to avoid.  I don't see how working in a realizability topos overcomes this objection either, from what I can understand of the definition.  Anyway, I must apologise for my clumsy presentation of what to me seems to be a deep philosophical, and perhaps unanswered, question as something rather trivial and uninteresting.  
> **username_5**: At the end of my answer I hinted how you can avoid choosing a computability structure: work in constructive logic, so that everything you do is computable (in any computability structure).  
> **username_6**: @TomEllis Your choice of computability structure is restricted if your set has some special structure. For example, on natural numbers, you want your computability structure such that addition and multiplication (and other stuff) are realized. This restricts your choice, and I'd expect the usual computability structure on natural numbers to be definable by something like: the smallest such that <some well chosent set of functions> are computable. | Also, when your set has some special structure, you want your $g$ to be an isomorphism.  
> **username_6**: @TomEllis And about axiomatization: it's the same as the one of the structure that your set has, except that all functions that appear in this axiomatizaton should be computable. Just like when you axiomatize topological groups, you ask that all operations (multiplication and inverse) are continuous, when you axiomatize computable groups, you ask that all operations are computable.  

---

### Answer by username_7 on 2017-12-01. Score: 4

The two papers below develop a notion of computability for arbitrary sets.
Interestingly even a notion of complexity theory can be defined for this model of computation.

[Cobham Recursive Set Functions and Weak Set Theories
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.](http://users.math.cas.cz/~thapen/CRSF_APAL.pdf)

[Subset-Bounded Recursion and a Circuit Model for Cobham Recursive Set Functions
Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.](http://users.math.cas.cz/~thapen/papertwo_revision.pdf)


---

### Answer by username_8 on 2017-12-02. Score: 0

There is a concept of complexity and computation over the reals. A textbook I would direct you to is: [https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817](https://rads.stackoverflow.com/amzn/click/0387982817)

I know of one lab that studies this specifically: <https://complexity.kaist.ac.kr/>

> **Comments:**
> **username_5**: That one is not particularly realistic as it implies that the Halting oracle is computable.  

---

### Answer by username_4 on 2017-12-01. Score: -1

This is similar to how we define computability in terms of Turing machines and then promptly forget about Turing machines. Since it turns out a Turing machine is as good a definition as any other, we use it as an anchor for an entire equivalence class of models, and we end up with the same class no matter which element we generate it from. Basically this is the Church-Turing thesis and it defines the set of computable bit strings.

Similarly, to define computability on a different set $S$, we anchor it with a particular partial function from bit strings to $S$. Actually it does not matter if this function is a bijection or an injection or any other type of function (for a case where we don't really want it to be an injection, consider a group defined by its presentation where we don't have a unique representation for its elements). It doesn't even have to be a surjection if we permit that singleton sets can be uncomputable. By composing this function with any computable bijection from bit strings to bit strings (a concept already defined), we get a definition of computability for $S$ that's invariant with respect to the function we originally picked (as long as we picked something reasonable). That is, a CT thesis for our set $S$. But if we don't pick a reasonable function, we get a different definition of computability.

This function also serves to define the computability of other functions with domain or range equal to $S$. By changing the range to $S$, keeping the domain as $\{0,1\}^\*$, we also get an $O(1)$-invariant definition of Kolmogorov complexity for $S$. And we can finally say that the function we have chosen is itself computable.

So I think the answer to your question is NO. We have to define computability for each set that we want to talk about, because there are non-equivalent definitions. Aside from a very technical or pedagogical discussion it shouldn't be necessary, since a reasonable person can imagine a reasonable definition independently.

But wait, let $S$ be a countably infinite set, and that's it. What's our reasonable definition of computability for $S$? Knowing that the set of bijections between $S$ and $\{0,1\}^\*$ is non-empty doesn't tell us which are reasonable. We're out of luck without more details.

And we may encounter multiple inequivalent but equally-reasonable alternatives. Suppose every tree has some number of red leaves and some number of green leaves, and that for every $r \in \mathbb{N}$ there exists exactly one tree with $r$ red leaves, and that for every $g \in \mathbb{N}$ there exists exactly one tree with $g$ green leaves. Both bijections are reasonable in the sense that we can count the leaves and distinguish the colors, and we can walk aimlessly around the woods counting leaves on trees until we find the tree with exactly $23$ green leaves, or the one with $23$ red leaves. It's not clear whether to identify a tree using its red leaf count or its green leaf count because this choice leads to inequivalent definitions of computability for sets of trees. If we instead make our definition by combining the counts with a computable pairing function bijective from $\mathbb{N}^2$ to $\mathbb{N}$ (having appropriately defined computability on $\mathbb{N}^2$), that also uniquely identifies each tree, but the situation is even worse because this is not a bijection between trees and $\mathbb{N}$, now maybe all computable sets of trees are finite!

So in order to avoid the entire discussion it should be understood not only that there exists a reasonable definition of computability on the set in question, but also that there is exactly one class of reasonable definitions.

I think the situation becomes a lot more interesting if we bring time complexity into the picture. Even when just considering integers, our choices matter more. For example, what if we wanted to represent each number as a sum of four squares? We can find such a representation, starting from a base representation, in expected quadratic time with access to randomness. Or instead, as a list of its prime factors, which may or may not be possible to compute in polynomial time. To the extent that we allow hard representations, we lose precision in time complexity. For example, we can't meaningfully say that some function $F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time if we have a representation of $\mathbb{N}$ that might require more than quadratic time to convert to or from a base representation. I think this perspective reveals that base representation is a somewhat arbitrary standard. (Standard in the sense that base representation is what anyone has in mind when they say something like "$F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time", if the underlying model is one that computes bit strings from bit strings and we're supposed to infer the meaning.)


---

