Computable functions on encoded structures

Computable functions on encoded structures#

At this point, we have seen a bit about one particular model of computation, leading to the definition of a 1# computable function. We also saw some mathematically natural algorithmic problems having to do with graphs, tiling, dominoes, and matricies. What we want to do at this point is to connect these two discussions. We also want to say in a more formal way what it means for one or another algorithmic problem to be decidable or undecidable.

Definition 1

A structure is a tuple

\[ \mathcal{S} = (S,R_1, \ldots, R_n, f_1, \ldots, f_m) \]

where \(S\) is a set, \(R_1, \ldots, R_n\) are relations on \(S\), each of some finite number \(n_R\geq 1\) of variables, and \(f_1, \ldots, f_m\) are functions on \(S\), each of some finite number \(n_f \geq 0\) of variables. Note that we allow \(n_f = 0\), and in this case \(f\) is called a constant symbol.

This is the standard notion of a first-order structure from mathematical logic.

The kinds of problems that interest us are where we are given a type of mathematical problem represented by a structure \(S\), and a target set \(T\subseteq S\). We are interested to know whether a given \(s\in S\) belongs to \(T\) or not.

Definition 2

Given a structure \(\mathcal{S}\), a 1#-encoding of \(\mathcal{S}\) consists of

A set \(\widehat{S} \subset Words\) of 1#-words. \(\widehat{S}\) must be decidable.
A one-to-one function \(\pi: S \to \widehat{S}\) called the coding map.
For each relation \(R\subseteq S^n\) a relation \(\widehat{R}\subseteq (\widehat{S})^n\). We require that \(\widehat{R}\) be 1#-computable. We also require that

\[ R(s_1, \ldots, s_n) \mbox{ iff } \widehat{R}(\pi(s_1),\ldots, \pi(s_n)). \]

For each function \(f: S^n\to S\) a function \(\widehat{f}: (\widehat{S})^n\to \widehat{S}\). We require that \(\widehat{f}\) be 1#-computable. We also require that

\[ \pi(f(s_1, \ldots, s_n)) = \widehat{f}(\pi(s_1),\ldots, \pi(s_n)). \]

An encoding of a structure has a lot of components, but to keep our notation short we usually abbreviate the whole thing by \(\pi\).

Another way to say this is that an encoding of \(\mathcal{S}\) is an isomorphic copy in which all parts of the structure are 1#-computable.

Example

Let

\[ \mathcal{N} = (N, 0,s) \]

be the most basic version of the natural numbers. Here \(N = \{0,1,2,\ldots\}\), \(0\) is a constant (a function symbol with \(n_0 = 0\) and with value \(0\)), and \(s(n)= n+1\) for all \(n\).

We next define one particular encoding of this structure which we’ll call the unary encoding.

We take \(\widehat{S} = \{\varepsilon, {\tt 1}, {\tt 11}, {\tt 111}, \ldots\}\).
\(\pi({\tt 1}^n) = n\). That is, \(\pi(\varepsilon) = 0\), \(\pi({\tt 1}) = 1\), \(\pi({\tt 11}) = 2\), etc.
\(\widehat{0} = \varepsilon\).
\(\widehat{s}({\tt 1}^n) = {\tt 1}^{n+1}\).

This completes the definition. We must check that the set \(\widehat{S}\) is computable; this is easy. And \(\hat{s}\) is also computable: a program for it is 1#.

There are other encodings of this same structure \(\mathcal{N}\). For example, we could drop the empty word from \(\widehat{S}\) and adjust the rest of the encoding apparatus. We also could decide to use binary numbers, and even there we have several options of how to regard binary numbers as 1# words.

Definition 3

Suppose we are given a structure \(\mathcal{S}\) and an encoding \(\pi\) of it.

A function \(f: S^n\to S\) is computable relative to the encoding if the isomorphic version of it is 1#-computable.

A relation \(R\subseteq S^n\) is computable or decidable if its isomorphic version is 1# computable.

Example

Let us return to the example of \(\mathcal{N}\) and the unary encoding of it.

The addition function \(f: N \times N \to N\) is computable, where \(f(n,m) = n+m\). A program which shows this is \({\tt move}_{2,1}\).
As we’ll see later, basically every function on the natural numbers which is encountered in standard mathematics is 1#-computable.
The following relations are decidable: first the set of prime numbers. Second, the set of pairs \((m,n)\) such that \(m\) divides \(n\) without a remainder.

Exercise 5

Check that the structure \(\mathcal{W} = (W,\varepsilon, \){\tt 1}, {\tt #},\(+)\) of 1#-words is decidable, where \(W\) is the set of all 1# words; \(\varepsilon\), 1, and # are the evident constants, and \(+\) is the function of two arguments giving their concantenation.

[This should be easy.]

Exercise 6

Show that if \(\mathcal{S}\) is a structure which has a 1#-encoding, then every finite subset of \(S\) is computable.

[Use proposition_finite_computable]

Exercise 7

The structure \(\mathbb{Z} = (Z,0, s, p)\) of integers has

\[ Z = \{\ldots, -2, -1, 0, 1, 2, \ldots\} \]

Here \(s\) and \(p\) are the successor and predecessor functions on the integers: \(s(n) = n+1\) and \(p(n) = n - 1\).

Your problems:

Find a 1#-encoding of \(\mathbb{Z}\).
Show that the addition function on the integers is 1#-computable relative to your encoding.

This might be messy and/or tedious, because you have to exhibit 1# programs as part of the encoding and also to represent addition. It is fine to be hand-wavy here. Soon we will have tools to make it easier to actually write programs. And for something tedious, it is usually sufficient to convince yourself that you could write the program.

Exercise 8

Let \(P\) be the set of pairs \((p,q)\) of 1#-words. We consider the structure

\[ \mathcal{P} = (P, a_1, a_{\#}, b_1, b_{\#}) \]

where

\[\begin{split} \begin{array}{lcl} a_1(p,q) & = & (p + 1, q)\\ a_{\#} (p,q) & = & (p +\# , q)\\ b_1(p,q) & = & (p , q + 1)\\ b_{\#} (p,q) & = & (p, q + \# )\\ \end{array} \end{split}\]

Find a computable encoding of this structure.

Exercise 9

If we want to discuss whether \(2\times 2\) matrix mortality is decidable, or whether \(3\times 3\) matrix mortality is decidable, it is natural to propose 1#-encodings. Let’s do this for \(2\times 2\) matricies.
Consider

\[ (\mathcal{M}_2, 0, times), \]

where \(\mathcal{M}_2\) is the set of \(2\times 2\) integer matrices, \(0\) is the \(2\times 2\) zero matrix, and \(times(M,N) = M\times N\).

A computable encoding of this structure includes a computable subset \(\widehat{S}\subseteq Words\), and an injection \(\pi: \mathcal{M}_2\to \widehat{S}\). Find such \(\widehat{S}\) and \(\pi\). (As always, there are many choices.)
What are the rest of the requirements on a computable encoding of this structure? You don’t need to give the program which corresponds to \(times\), since that would be quite tedious.

Exercise 10

Let \(\mathcal{G}\) be the set of finite graphs whose set of vertices is of the form \(\{1,2, \ldots, n\}\) for some \(n\). We make this into a structure. There are no relations or functions, just the set by itself. What is an encoding of this structure? What does it mean to say that the subset \(C\) of graphs which contain a cycle is a decidable set relative to an encoding?