In David Deustch and Chiara Marletto's Constructor Theory of Information (section 5) a set of attributes $S$ is defined as distinguishable if the task of transforming each attribute $x$ of $S$ into an attribute $\Psi_x$ is possible, and the set $\left\{\Psi_x\right\}$ is an information variable (a clonable computation variable).

It is not explicitly stated that $x \ne y \rightarrow \Psi_x \ne \Psi_y$ for $x, y \in S$, but it seems pretty obvious that if this is not the case (i.e., if two different attributes in S are transformed to the same attribute), then $S$ would not be distinguishable (at least not in the intuitive sense, which I believe is supposed to correspond to this formal definition).

Is this requirement implied in some way by how it is formulated, or in the fact that $\left\{\Psi_x\right\}$ is an information variable, is it simply missing from the paper, or is it not actually a requirement for distinguishability?

I know that to be a variable, the members of $\left\{\Psi_x\right\}$ must all be disjoint, but since a set cannot contain duplicate elements, I've been interpreting this as throwing away duplicate values of $\Psi_x$. For instance if $S = \left\{a, b, c\right\}$ and the task is defined as the transformations $\left\{ a \rightarrow r, b \rightarrow s, c \rightarrow r\right\}$, then I interpret $\left\{\Psi_x\right\}$ as just $\left\{r, s\right\}$. Is that incorrect interpretation?


1 Answer 1


I feel that the main problem here is Deutsch and Marletto not being clear, hopefully this will change as more people scrutinise the paper.

A possible explanation for our problem is that when they give the definition of distinguishability, they meant to say that for all choices of information variable $\left\{\Psi_x \right\}$, $$\left\{x\rightarrow \Psi_x | x\in X \right\}$$

is a possible task.

If we take this as our definition then I reckon the following holds:

To prove a set of attributes $X$ as distinguishable it suffices to prove that $\left\{x\rightarrow \Phi_x | x\in X \right\}$ is a possible task for a single choice of $\left\{ \Phi_x \right\}$ such that $\forall(x\neq y \in X)(\Phi_x \neq \Phi_y)$. After finding this we can use the interoperability property of information (postulate 3 given in the next section) to permute to all other information variables. I think you can still do this even if the information variable has fewer members than $\left\{ \Phi_x \right\}$ by defining the new information variable to be a coarsening of $\left\{ \Phi_x \right\}$. (that is, some of the attributes in the new variable are unions of the $\Phi_x$).

Let me know if that makes sense, I've found this paper very easy to misinterpret so I could have made a mistake.

  • $\begingroup$ Seems like a reasonable idea. I haven't gone back to validate your proof, but it appears sound. Thanks! $\endgroup$ Apr 30, 2015 at 12:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .