Defining computable functions on arbitrary sets

Question

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to exhibit a Turing machine that computes it. In the case where the function is not from strings to strings, something about this bothers me.

I will introduce the problem with a simple example. Suppose that I define a function from binary trees to binary trees, and I want to show, formally, that it's computable. To do that I would have to exhibit a Turing machine that computes it. Since binary trees are not strings, I first have to design a string representation of binary trees. For example, I could represent the tree

as ((*,*),(*)). Having done this, I can then pass binary trees to Turing machines in string form, and get trees back in string form, no problem.

But here's my problem: the representation of binary trees as strings is itself a function (in fact a bijection) from binary trees to strings. How can I know formally that this function is a computable one?

On an intuitive level I have no problem seeing that it is, but on a formal level I can't exhibit a Turing machine to verify it, because then I would need a string representation of binary trees, and we quickly get into an infinite regress. For simple things like binary trees the computability of the representation is obvious, but for more complicated sets it might not be.

Can this circle be squared --- is there a formal definition of computability for functions of arbitrary countable sets that might not admit an obvious mapping to strings of symbols?

Additional thoughts

Here is another way of explaining my question: we might choose to define a model of computation that operates inherently on trees or some other set rather than strings. Indeed, many such models of computation have been proposed, including the lambda calculus and combinator calculi (which are arguably more naturally seen as operating on trees rather than strings), the recursive functions (which operate on integers), and various cellular automata (which operate on infinite strings or two dimensional lattice configurations, rather than finite strings). It's only really historical accident that led the string-based Turing machines to become the gold standard against which other models of computation are judged.

The problem is that without being able to talk about computable mappings between these sets, it's not strictly formally possible to say whether these other models of computation are equivalent to Turing machines or not. While it usually doesn't raise any practical problems to just think of everything in terms of string representations, it seems dissatisfying that our theory of computation doesn't treat all models of computation equally, but instead privileges those whose input and output are from a particular kind of set.

So really my question is whether a theory of computation exists has been formulated that is model-agnostic, in precisely this sense of not privileging one particular kind of set for input and output. It's quite an abstract question, motivated more by a desire for formal niceness than by any practical concerns.

One suspects, for example, that the category theorists might have done some work in this direction. This is because category theory tends to talk about the properties of functions without talking much about the sets they map, so a "category of computable functions" would probably not know or care whether its underling objects were sets of strings or something else. This is an approach I would be particularly keen to read about if it exists. (I've asked another question, specifically about the category theory aspect, over at MathOverflow.)

Answer 1

Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:

• $\operatorname{vertex}(x)$, which is true if $x$ is a vertex.

• $\operatorname{tree}(x)$, which is true if $x$ is a tree.

• $\operatorname{appears}(x,T)$, which is true if $x$ is a vertex that appears in the tree $T$.

• $\operatorname{edge}(x,y,T)$, which is true if $x,y$ are two vertices in $T$ which are connected by an edge.

(We don't really need both $\operatorname{vertex}$ and $\operatorname{tree}$, but we do need to be able to express being in the domain of the structure, i.e., either a vertex or a tree.)

Formally speaking, to complete the definition of the structure we have to specify an encoding of the domain, either as strings or as natural numbers (this is an arbitrary choice which doesn't make much difference). Under any reasonable encoding, all the relations above will be computable, and so we have a computable structure.

A computable presentation of this structure is an isomorphism which maps this structure to another computable structure. This mapping has to be an isomorphism of structures, but it doesn't have to be computable. A computable structure $\mathcal{A}$ is computably categorical if whenevever $\mathcal{A}$ is isomorphic to a computable structure $\mathcal{B}$ (by a computable presentation), then there is a computable isomorphism between the two structures.

Using this vocabulary, what you might be asking is whether the computable structure of finite trees is computably categorical. (There is actually more freedom in your question, since you might want to use a different relational structure.) Some simple computable structures are computably categorical (for example, the rationals with the order relation, and the natural numbers with the successor function) and some aren't (for example, the natural numbers with the order relation), see Computable structures: presentations matter by Shore.

Answer 2

Unfortunately, as Raphael says, the answer is no.

The formalist answer is that computability is defined for functions $f:\{0,1\}^* \to \{0,1\}$; it's not defined for functions on other domains.

A possible motivation is that classical computability theory is concerned with what can be computed on a digital computer. A digital computer operates on bits. Thus, it's perhaps not surprising that classical computability theory is concerned with computations where the input is a binary string. We can choose to interpret that bit-string as a representation/encoding of a tree, but that interpretation is up to us (humans). Computers have no way to accept a tree directly as input; they can only accept a sequence of bits on their input.

If we want to reason about computations on trees, we define an input encoding $e:\mathcal{T} \to \{0,1\}^*$ that maps a tree $T$ to a bit-string $e(T)$. Then, we feed the bit-string $e(T)$ as the input to the computer. Formally, the computer accepts the bit-string $e(T)$ as input, not $T$ itself. Once we have fixed an input encoding, this allows us to transfer results about computability on bit-strings to computability on trees.

Formally, you could define a notion of computability on trees as follows: we could say that a function $f:\mathcal{T} \to \{0,1\}$ is computable (with respect to the input encoding $e$) if there exists a computable function $g:\{0,1\}^* \to \{0,1\}$ such that $f = g \circ e$. Of course, those results may depend on the input encoding. (In practice it doesn't depend on the input encoding as long as you choose a "reasonable" encoding, because in practice reasonable input encodings are fairly trivial and don't hide any non-trivial computation; or formally, if $e_1,e_2$ are any two "reasonable" input encodings, usually the mappings $e_1(e_2^{-1}(\cdot))$ and $e_2(e_1^{-1}(\cdot))$ are computable, and obviously so, which means that the choice of input encoding doesn't affect which functions are considered computable, as long as you choose a "reasonable" input encoding. However there's no formal definition of what counts as a "reasonable" input encoding.)

I realize this might seem highly unsatisfactory. I do sympathize. I think that's a reasonable reaction.

That said, let me share a perspective that might help you feel a little better about the situation. Computability theory is about what functionality can be computed: given a specification of the desired input-behavior of a computer, it lets us determine whether it's possible to find an implementation that achieves that behavior. Usually we are interested in non-trivial specifications where it's not obvious whether such a specification is even attainable.

Once you add the input encoding, we think of something external (e.g., a human) as applying the input encoding before the data is given to the computer. Then, computability theory is only concerned with what the computer can compute, not what a human can do.

The input encoding usually has nothing very interesting going on. Usually, we can easily identify a straightforward input encoding that maps from, say, trees to bit strings. It's not a situation where we have only a specification and we're not sure whether it is possible to implement it. Rather, we usually can immediately identify an implementation, and it is obvious that a human could apply it if they wanted -- so there is no question about whether the input encoding is achievable. (If there is a question, we choose a different input encoding until we have one that is self-evidently achievable.)

So, computability theory concerns itself with a situation where we have a specification of desired behavior and we want to know whether it is attainable. Input encodings don't fall into that situation; usually we already know they are attainable, so the core question of computability doesn't even come up. We don't need to ask whether the input encoding is achievable because we already know how to achieve it. Ultimately, computability theory is just a tool to answer questions, and any question you might have about computability on trees seems to either fall out naturally as a consequence of computability on strings, or else isn't well-posed; so there's not really any loss of generality by focusing on computability on strings.

I'm not sure if that will help you feel any better about the situation.

Answer 3

In addition to the other answers given you might look at higher type computability which studies certain set like things and what it means for functions to be computable between them. Domain theory gives a set theoretic answer to what functions you can compute in the lambda calculus and in things like PCF. In particular you can ask questions like what functions are computable on $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$ or $((\mathbb{N} \to \mathbb{N}) \to \mathbb{N}) \to \mathbb{N}$

A neat fact is that if one consideres "$\to$" to refer to the total functions then elements of $((\mathbb{N} \to \mathbb{N}) \to \mathbb{N}) \to \mathbb{N}$ have decidable equality!