Undecidability and the developability of permutoids and rigid pseudogroups


Bridson, M
Wilton, H

Publication Date: 

20 March 2017


Forum of Mathematics, Sigma

Last Updated: 



A permutoid is a set of partial permutations that contains the identity and
is such that partial compositions, when defined, have at most one extension in
the set. In 2004 Peter Cameron conjectured that there can exist no algorithm
that determines whether or not a finite permutoid based on a finite set can be
completed to a finite permutation group, and he related this problem to the
study of groups that have no non-trivial finite quotients. This note explains
how our recent work on the profinite triviality problem for finitely presented
groups can be used to prove Cameron's conjecture. We also prove that the
existence problem for finite developments of rigid pseudogroups is unsolvable.

Symplectic id: 


Download URL: 

Submitted to ORA: 


Publication Type: 

Journal Article