Defining computable functions on arbitrary sets 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 &quot;category of computable functions&quot; 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.)
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.