In the paper Constructor Theory of Information, page 11. We are told that a set $X$ of attributes are distinguishable if the following is a possible task:

$$\{ x\rightarrow \Psi_x | x\in X \}$$ where $\{ \Psi_x \}$ constitute an information variable. It is not clear if it is supposed to be a possible task for all choices of $\{ \Psi_x \}$ or just some (see this post). We define $x\bot y$ to mean the same as $\{ x, y \}$ being distinguishable. The rest of the paper frequently relies on $y\subseteq z \Rightarrow y \not \bot z$ to reach various conclusions but I can't see how this can be the case. Here's what I think is a proof for the opposite: $y\subseteq z \Rightarrow y \bot z$

We start with two attributes $y$, $z$ satisfying $y \subseteq z$. To show that $y\bot z$ we need to show that the following is a possible task $T$ for $\Psi_x$ an information variable; $$T=\{ z \rightarrow \Psi_z , y \rightarrow \Psi_y \}$$

Now consider the constructor $C$ which when presented with any state in attribute $z$ ,transforms it into the state $\Psi_z$. We need not define what it does in other cases. I think it is fair to say that such a constructor is possible to make: because it always outputs the same thing, we could make one by painting "$\Psi_z$" on a plank of wood.

The paper Constructor Theory defines a constructor as capable of performing a task $T$ if, "whenever it is presented with substrates in a legitimate input state of $T$, it transforms them to one of the output states that $T$ associates with that input". From this it seems to follow that our $C$ from above is capable of performing $T$. It trivially works for a state $a\in z-y$. And if $C$ is presented with an $a\in y$ it will transform it to $\Psi_z$, but this satisfies the rules of the task because we only need it to transform to one of the outputs associated with $a$ (which are either $\Psi_y$ or $\Psi_z$). Hence we have shown that $T$ is possible and hence $y$ is 'distinguishable' from $z$.

What's wrong with my proof? How does one derive $y\subseteq z \Rightarrow y \not \bot z$?

  • $\begingroup$ Perhaps this should be a Physics Overflow question? It's borderline. The only other constructor theory question is on this site. $\endgroup$
    – Ed Ayers
    Apr 24, 2015 at 17:27

1 Answer 1


Variables must have disjoint members, so the criterion

where {Ψx} constitute an information variable.

in the definition of distinguishability is not met by your {Ψx} which contains overlapping members Ψz and Ψy.


You must log in to answer this question.

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