What is a computable function?

Question

If $f:\Sigma^* \to \Sigma^*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^*$ writes $f(w)$, $\forall w\in\Sigma^*$, then we call $f$ as computable function.

But in general when a talk about a function from some domain like $\mathbb{N}$, set of all graphs, etc., is computable, what it mean exactly in terms of turing machine and encodings? I mean when we encode an element from domain of the function we may have two different strings in $\Sigma^*$ represent the same element of the domain and some string may not represent an element from the domain at all, so how we rigorously define computability of $f$?

Answer 1

When we define a model of computation, depending on the model there will be some kind of "basic object".

• For Turing machines, the basic objects can be taken to be strings on $\{0,1\}$.

• For register machines, the basic objects can be taken to be natural numbers

However, there is a very standard way to use a general model of computation to "compute" other things. To do this, we need to represent objects of our new type $T$ via elements of the set $B$ of basic objects. This is also called encoding and numbering.

There are two dual ways to approach this problem, via representations and via numberings. A key point is that the representation functions and numbering functions are not themselves "computable" by the model of computation. The purpose of these functions is to translate other objects into a form that the model of computation is able to work with, and then translate the results of the model of computation once it is finished computing.

Representations

If $B$ is our set of basic objects and $T$ is the set of things we now want to compute with, a representation is a function $f\colon T \to B$.

We say that a function $G \colon T \to T$ is computable relative to the representation $f$ if there is a computable function $\phi \colon B \to B$ so that, for all $x \in T$, $$ \phi(f(x)) = f(G(x)). $$

Intuitively, this says: To compute $G(x)$, first translate $x$ to a basic object $f(x)$ then run $\phi$ on $f(x)$. The result will be the representation of the element $G(x)$ that we wanted to compute.

Note that the definition of a representation does not require $f$ to be surjective, only that it be defined on all of $T$.

The concept of a representation can be generalized so that the same object may have more than one representation. Now we just require $f$ to be a multifunction from $T$ to $B$, so that for each $x \in T$ we have a nonempty set $f(x)$ of basic elements that each represent $x$. We now require that, for all $x \in T$, $$ (\forall z \in f(x))[ \phi(z) \in f(G(x))]. $$

Example

Suppose we want to compute a function from finite graphs to finite graphs. We can make a representation of a finite graph $G = (V_G, E_G)$ by sending $G$ to the pair $(n, e, m)$ where $n = |V_G|$, $e = |E_G|$, and $m$ is a binary string of length $m\cdot e$ that tells whether each vertex is incident to each edge. We can represent $(n,e,m)$ as a binary string or a natural number as we desire.

Similarly, we can represent the collection of integers by mapping an integer $p$ to a pair $(n,m)$ of natural numbers so that $p = n-m$. This is an example where we could let the representation be a multifunction.

We can also extend representations to higher types. For example, via standard oracle computation methods, we can use our basic model of computation to compute functions that take an infinite binary sequence as input and produce an infinite binary sequence as output. Then, using representations, we can use these oracle computations to compute functions from $\mathbb{R}$ to $\mathbb{R}$, etc.

One reference on representations is: Klaus Weihrauch (2000), Computable analysis, Springer, ISBN 3-540-66817-9

Numberings

The dual concept of representation is numbering. A numbering is a partial surjective function $h \colon B \to T$. We say that a function $G \colon T \to T$ is computable relative to a numbering $h$ if there is a computable function $\phi$ so that, for all $z \in T$ and all $x \in B$ with $h(x) = z$, we have $$h(\phi(x)) = G(z).$$ Intuitively, this says that if I have a name $x$ for some element $z = h(x)$, then to compute $G(z)$ I can just compute $\phi(x)$, and this will be a name for $G(z)$.

The idea of numbering is the dual of the idea of representation. For example, with our graph representation above that takes $(V_G, E_G)$ to $(v,e,m)$, the corresponding numbering would take a basic object $b$, attempt to view $b$ as a triple $(v,e,m)$, and return the appropriate graph. If $b$ does not encode a triple of that form, then the numbering will not give a value for $b$ - this is why the numbering may be a partial function. However every element of $T$ has some name, so the numbering will be surjective.

Numberings are a very classical topic in computability. One reference is "Theory of Numberings", Yuri L. Ershov, in Handbook of Computability Theory (1999), E.r. Griffor (ed.), Elsevier.

Answer 2

Notation: below I write "$\hat{\rightarrow}$" and "$\hat{\twoheadrightarrow}$" for "partial function" and "surjective partial function," respectively.

---

We demand the obvious requirements: that the machine behave correctly on all strings which are "meaningful." We don't demand anything else.

Specifically, an encoding is a map sending strings to objects. This map might be partial (= not every string is a valid name) and non-injective (= some objects might have many names), but it does have to be surjective (= every object needs a name).

A machine then computes a function $f$ in the sense of this encoding if it behaves correctly on names: it sends a valid name for $a$ to a valid name for $f(a)$. Beyond this requirement, we don't care what it does:

• Given two different names for the same input object $a$, it might output two different names for $f(a)$ - or, it might output the same name for $f(a)$.

• Given a non-name as input, we don't care what it does at all.

---

Formally, suppose we have a partial function $f:A\hat{\rightarrow} B$ (say, naturals to graphs) and encodings (= partial, surjective, not-necessarily-injective functions) $$\mu,\nu:\Sigma^*\hat{\twoheadrightarrow} A,B$$ of $A$ and $B$ respectively.

• Note: the definition of "encoding" above says that not every string needs to be a name for something, and something can have more than one name, but everything must have at least one name.

Then a Turing machine $\Phi$ computes $f$ in the sense of $\mu,\nu$ if and only if $$\forall \sigma\in dom(\mu)[\Phi(\sigma)\in dom(\nu)\mbox{ and }\nu(\Phi(\sigma))=f(\mu^{-1}(\sigma))].$$ That is, whenever $\sigma$ names $a\in A$ (in the sense of $\mu$), then $\Phi(\sigma)$ halts and is a name for $f(a)$ (in the sense of $\nu$).

In particular:

• Given a valid $\mu$-name, $\Phi$ has to halt and spit out a valid $\nu$-name; and $\Phi$ needs to spit out a correct name (if $\sigma$ names $a$ then $\Phi(\sigma)$ needs to name $f(a)$).

• On a string which isn't a $\mu$-name, we don't demand anything from $\Phi$: it could not halt, it could halt and spit out a valid $\nu$-name, it could halt and spit out gibberish, we don't care.

---

By going a bit more abstract, we can talk about general representations. This language winds up being very useful down the road, and it's not much of a generalization from where we already are.

Suppose I have sets $A,B,C,D$ and encodings $\mu: C\hat{\twoheadrightarrow} A$ and $\nu: D\hat{\twoheadrightarrow} B$. ($C$ and $D$ are playing the role of $\Sigma^*$, here.) Then we can talk about a function $F: C\hat{\rightarrow} D$ representing a function $f:A\hat{\rightarrow} B$ as follows: $$F\mbox{ represents }f\iff\forall x\in dom(\mu), f(\mu(x))\cong\nu(F(x)).$$ Here, "$\cong$" is identity of partial terms: that is, $f(\mu(x))$ is defined iff $\nu(F(x))$ is, and if they're defined then they're equal.

To compute $f$ (in the sense of $\mu$ and $\nu$) is just to compute some function representing $f$ (assuming this makes sense - that is, assuming we already understand what it means to compute a function from $C$ to $D$).

This level of abstraction can be a bit tedious, but I think it gives a nice clear picture of what's going on "under the hood" - and it turns out to be essential in many topics later on, such as the theory of represented spaces.