What is a reasonable representation/encoding of objects? [closed]

Question

Question

What is a reasonable representation of objects (for computability)?
What is the criteria that we should apply to see if a representation is reasonable?

This answer by Andrej suggests that the representation should be workable and "workable" here means that the basic operations associated with those objects should be computable over those representations. More formally, as I understand it, he is saying that we are not representing objects alone but a structure of objects that comes with some operations, and a representation should allow us to compute the operations coming from that structure. After we pick a representation for that structure, we can start taking about computing other operations.

However I don't feel that answer is satisfying for two reasons:

1. We already make a decision about what to be computable when deciding what operations are basic. For example, I feel that Andrej in his answer already decided that equality is not going to be decidable.

2. Objects don't really come with an associated structure. We think of the same objects as belonging to several different structures. Sometimes the model of computation cannot support all of the operations of the natural structure associated with objects, e.g. for real numbers one would probably want at least addition, multiplication, order, and equality. This has lead to models of computation like real-RAM and BSS though one can argue that they are not practical.

I feel that from constructive perspective, what is important is how the objects are constructed. The structures and operations come later. A reasonable representation should allow us to obtain enough information about the way an object is constructed and the computability of any other operation should be based on computability of of them from this information.

So my main question:

Why we need a reasonable representation of objects (e.g. real numbers) support anything more than a mechanism to give us information about the construction of those objects (arbitrary good enough approximations)? Why we need a reasonable representation to support the operations of a structure on those objects (e.g. addition on real numbers)? And how can we decide which operations are essential and which ones are not (e.g. why addition on real numbers and not equality of real numbers)?

---

Background

Many computational models usually deal with very basic data types. For example, a Turing machine works on a string of symbols from a fixed finite alphabet.

However, often we need to perform computation on other kind of objects, e.g. natural numbers, rational numbers, graphs, Turing machines, real numbers, etc. We encode objects as objects of the basic data types that the machine is designed to work with. More formally, a representation is a function from a basic data type supported by the machine to the set of objects we want to talk about.

Examples:

• We can encode natural numbers as strings of bits of their binary representation: $\langle n \rangle = (n)_2 $.

• We can encode integers numbers using pairs of natural numbers and a pair like $\langle n,m\rangle$ represents the integer $n-m$.

• We can encode rationals using a pair of a natural number and an integer $\langle \frac{p}{q}\rangle = \langle p, q\rangle$.

Each object can have several names, and we can define the equality between these names, e.g. $\langle \frac{p}{q}\rangle = \langle \frac{p'}{q'}\rangle$ iff $pq'=p'q$ to say that two names refer to the same object.

More examples:

• We can represents a graph with vertices $\{1,\ldots, n\}$ by the number of vertices $n$ and its list of edges. Or we can represent it using its adjacency matrix.

• We can represent a Turing machine as a labeled graph.

The natural representations that one normally comes up with are equally good for computability (but not always for complexity) as we can convert any of them to other ones computably.

However one can also define more complicated representations: for example, we can represent a Turing machine as a labeled graph plus a proof in ZFC telling us if it is a halting when we have one. But we can also define a representation of Turing machines as a labeled graph plus one bit telling us if the machine halts on blank tape. This representation doesn't seem to be reasonable, e.g. it allows us to decide a Turing machine halts or not which is undecidable using usual representations, we also don't know how give an Turing machine as an input in practice as it would need us to know the answer to the halting problem on that machine. It give a sense of why this representation is not suitable, however it is still not easy to articulate why the representation is unreasonable (at least for me).

The explanation is usually along the lines that we take a weakest workable representation. Let me first explain what weakest means here: weakest means that any other workable representation can be computably converted to this representation. It seems a reasonable condition. However "workable" is bit vague and complicated here, for Turing machines one normally means something like the representation satisfies SMN and UTM theorems, however articulating why is not easy (at least it is not for me).

For computability on finite objects the problem is not big (and therefor the issue is completely avoided usually in introduction to computability and complexity): someone who is not familiar with these issues will normally use a representation which satisfies these conditions and is equivalent to other reasonable representations of the objects.

A similar issue comes up sometimes in complexity where it is not clear if there is a weakest workable representation: some algorithms work better with one representation, others work with other representation and all of these representations are considered reasonable (e.g. adjacency matrix, incidence matrix, etc. for graphs). Often the issue of representations and reasonable representations is avoided (one might say somewhat swept under the carpet) by saying that we define a problem not the objects but on a fixed representation of the objects. So a graph problem is not about graphs but about a particular representation of them.

However when we move to computability over objects that are inherently infinite, e.g. real numbers, the issue becomes more serious. If a person unfamiliar with computability over real numbers tries to come up with a representation the first representation is likely to be the decimal/binary expansion of the number which is not good for various reasons, e.g. even addition is not computable. Another representation might allow us to compute addition but not another function, or say equality with $0$. Yet another representation might allow us to compute equality to $0$ but not addition. And it is not even as clear if there is a weakest "workable" representation and/or what does we mean by "workable".

(There is also an issue of computability in what model which I will avoid for this question.)

Answer 1

You are touching on some very interesting basic questions about mathematics in general. Do we construct mathematical objects and later discover their structure, or do we construct objects with a specific structure in mind? I think the answer is not simple. Sometimes we "design" structures to order, and sometimes we discover them. I believe the quarternions were discovered, but at the same time Hamilton knew what sort of structure to look for. So I think your observation that we discover the structure of the objects we constructed has a lot of merit. But why do we discover some objects and not others? What makes the ones we pay attention to important and interesting? Presumably their structure.

Let me clear up something about equality versus addition. They have exactly the same status. The reals are equipped with equality, which is a binary relation, and they are also equipped with addition, which is a binary operation. We make no assumptions about equality being decidable, or not decidable, and neither to we make any assumption about addition being computable. We just state the axioms for the reals: they form a structure consisting of such-and-such relations and operations, satisfying such-and-such axioms. Then we ask whether such a structure exists in our (realizability) model. If it does, then we have an implementation of its parts. Addition is implemented by a program which takes realizers for two reals and computes a realizer for their sum. But how is equality implemented?

Equality is a binary relation, which is just a predicate on a cartesian product. So we might as well think about how to implement a predicate on a set. Well, there are two views of predicates. The first one is that a predicate $P$ on a set $X$ is just a subset $P \subseteq X$. The second one is that it is a map $P : X \to \lbrace 0, 1 \rbrace$. In intuitionistic mathematics, we have to replace the booleans $\lbrace 0, 1 \rbrace$ with the set of all truth values $\Omega$, which is much larger. In fact $\Omega$ is so complicated that it does not exist in the simple realizability models (although it exists in a realizability topos), which is a fancy way of saying that it cannot be implemented (feel free to have a go: implement the initial complete Heyting algebra; mind you, it has to have suprema of families indexed by atbitrary datatypes). So in general we cannot implement predicates as maps into the subobject classfier. We can of course implement them as subobjects, but that is rather useless, e.g., equality on $\mathbb{R}$ would be implemented as the map $x \mapsto (x, x)$.

Fortunately, certain pieces of $\Omega$ still exist in realizability models. If a predicate $P : X \to \Omega$ happens to factor through such a piece of $\Omega$, then we get to implement its classifying map. Some examples:

• the booleans $2 = \lbrace p \in \Omega \mid p \lor \lnot p\rbrace$ are familiar to every programmer, and most programming languages have the corresponding type bool. A predicate $P : X \to 2$ is knows as decidable and can be implemented as a map into bool. All this is familiar.

• the semidecidable truth values $\Sigma = \lbrace p \in \Omega \mid \exists f : \mathbb{N} \to 2 . p = (\exists n \in \mathbb{N} . f n = 1)\rbrace$ are those truth values that are equal to an existential quantification over $\mathbb{N}$ of a decidable predicate. They are around, not every programmer knows about them, but theoretical computer scientists are of course familiar with semidecidability. A semidecidable predicate $P : X \to \Sigma$ can be implemented as a map P : X -> (nat -> bool): it takes a realizer x for $x \in X$ and returns a realizer f : nat -> bool of some $f : \mathbb{N} \to 2$ such that $x \in P$ is equivalent to $\exists n . f n = 1$. This is less familiar and less useful.

• the classical truth values $\Omega_{\lnot\lnot} = \lbrace p \in \Omega \mid \lnot\lnot p = p\rbrace$ exist in a category of assemblies but not in a category of modest sets. So we are reaching the limit of what can be implemented. The implementation of $\Omega_{\lnot\lnot}$ is silly, because it is implemented by the unit type. In other words, a classical predicate $P : X \to \Omega_{\lnot\lnot}$ is implemented by a function which always returns the unit (). And I am not making this up. I am telling you what the realizability interpretation gives as a result.

It just so happens that $=$ on reals is not classified by a map into $2$, but it is classified by a map into $\Omega_{\lnot\lnot}$. So in principle one could implement equality as a map which always returns the unit (). That's useless. Perhaps $=$ is classified by a map into a smaller part of $\Omega$? Yes, it is a theorem that inequality $\neq$ is classifed by a map into $\Sigma$, so we can do better and implement $\neq$ as a map neq : real -> real -> (nat -> bool) which takes (realizers of) two reals $x$ and $y$, and returns a map f : nat -> bool which attains true iff $x \neq y$. But this is actually a very sensible thing: neq x y n tests x and y for inequality "up to precision n". That's how people actually implement exact real arithmetic.

I think a lot of confusion arises from the fact that people speak about "computable" relations without telling us wha that means. And when they do, they usually end up defining decidable relations. But that's just a very limited view of relations. There are semidecidable relations, and $\Pi^0_2$ relations, and arithmetical relations, etc.