What about groups with unsolvable word problem? These were originally constructed, independently by Novikov and Boone, using finite presentations derived ultimately from codifications of Turing machines with unsolvable halting problems (It is relatively easy to get semigroups with unsolvable word problem in this way. The hard part of the construction involves the use of HNN-extensions to convert them into group presentations.) It is difficult to envisage any natural associated action of such groups.