Undecidability of the free adjoint construction (Q1410542): Difference between revisions

Given a category \(\mathcal{C}\), the authors have elsewhere [\textit{R. Dawson, R. Paré} and \textit{D. Pronk}, Adv. Math. 178, 99-140 (2003; Zbl 1030.18001)] shown how to add right adjoints freely to all arrows in \(\mathcal{C}\) to obtain a 2-category \(\Pi_2\mathcal{C}\). The adjoint arrows correspond to arrows in \(\mathcal{C}^{\text{op}}\) and the units and counits freely added yield the 2-cells of the 2-category after dividing out by an equivalence relation generated by the `interchange law'. The equivalence relation on the resulting diagrams used to construct \(\Pi_2\mathcal{C}\) is here shown to be undecidable for certain choices of \(\mathcal{C}\). This is proved by showing that the problem of deciding whether two 2-cells with different representatives are, in fact, equal is equivalent in those cases to the halting problem for the abacus or register machine.