patternMinor
Defining computable functions on arbitrary sets
Viewed 0 times
computablearbitraryfunctionssetsdefining
Problem
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
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
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
Solution
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.
-
$\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.
Context
StackExchange Computer Science Q#88610, answer score: 5
Revisions (0)
No revisions yet.