5
$\begingroup$

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

enter image description here

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.)

$\endgroup$
  • 3
    $\begingroup$ The answer is rather simple and unsatisfactory: as far as (classic) computability theory is concerned, the string is the tree. That image you draw is something for human convenience; it is not covered by computability models, and it doesn't have to be. $\endgroup$ – Raphael Feb 26 '18 at 12:36
  • $\begingroup$ @Raphael that makes sense, and chimes with what I know about classic computability theory. But the feeling of being unsatisfactory is indeed quite intense, and also has the feeling (to me at least) that it ought to be fixable somehow. $\endgroup$ – Nathaniel Feb 26 '18 at 13:26
  • $\begingroup$ You can also design an API for directly accessing the tree. For example, there could be a function that returns an arbitrary vertex of the tree (as an ID), and another one which returns all neighbors of a given vertex. It's really up to you how to design the API. While the exact definition will not affect computability, it could well affect complexity. $\endgroup$ – Yuval Filmus Feb 26 '18 at 18:28
  • 1
    $\begingroup$ Modeling questions cannot be expressed formally, since modeling is the link between our informal and intuitive notions and the formal world of mathematics. $\endgroup$ – Yuval Filmus Feb 27 '18 at 11:53
  • 1
    $\begingroup$ As I read you, the question underlying your question is the one Tom posed here. If so, I think you will find Andrej's answer instructive. $\endgroup$ – Jason Hemann Jun 12 at 14:24
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, this is super helpful. Effective model theory might itself be the answer to my question (which is not really about binary trees at all, but about how to even talk about computable mappings between sets that are not strings). I will look into effective model theory more deeply, but from a naïve point of view the tricky part of my question seems to be in your phrase "reasonable encoding." Is a that something that can be defined formally, or do we still need to use our judgement about what counts as reasonable and what does not? $\endgroup$ – Nathaniel Feb 27 '18 at 10:15
  • $\begingroup$ It's an informal phrase. You gave such an encoding in your question. As explained in the other answer, such an encoding is really part of the definition of the computable structure. $\endgroup$ – Yuval Filmus Feb 27 '18 at 10:52
  • $\begingroup$ I added some text to the end of the question, which might help to explain why I find that unsatisfying. (That dissatisfaction is really at the heart of my question.) But I do appreciate this answer all the same, though, it's really helpful to know about this stuff. $\endgroup$ – Nathaniel Feb 27 '18 at 11:15
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for the effort to make me feel better! It doesn't really though, because my question is motivated more by a desire for precision of thought than by practical issues. I have some more thoughts following on from this, which I've edited into the question; +1 $\endgroup$ – Nathaniel Feb 27 '18 at 10:41
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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