A. Markoff (On the impossibility of certain algorithms in the theory of associative systems) and E. Post (Recursive Unsolvability of a Problem of Thue) provide examples of a finitely presented monoid with non-solvable word problem — or at least, so I read in various sources. I do not have access to any copy of Markoff's paper, and Post's (accessible via link above) is so verbose in his description that I cannot discern the actual presentation of the monoid in question.
Could someone provide a presentation in "modern notation" of such a monoid? e.g., $\langle a,b | a^3=b^3\rangle$. Thanks.
The group with 10 generators $\{a,b,c,d,e,p,q,r,t,k\}$ and the following 27 relations has an unsolvable word problem:
\begin{align} p^{10}a &= ap \\\ p^{10}b &= bp \\\ p^{10}c &= cp \\\ p^{10}d &= dp \\\ p^{10}e &= ep \\\ aq^{10} &= qa \\\ bq^{10} &=qb \\\ cq^{10} &= qc \\\ dq^{10} &= qd \\\ eq^{10} &= qe \\\ ra &= ar \\\ rb &= br \\\ rc &= cr \\\ rd &= dr \\\ re &= er \\\ pacqr &= rpcaq \\\ p^2adq^2r &= rp^2daq^2 \\\ p^3bcq^3r &= rp^3cbq^3 \\\ p^4bdq^4r &= rp^4dbq^4 \\\ p^5ceq^5r &= rp^5ecaq^5 \\\ p^6deq^6r &= rp^6edbq^6 \\\ p^7cdcq^7r &= rp^7cdceq^7 \\\ p^8ca^3q^8r &= rp^8a^3q^8 \\\ p^9da^3q^9r &= rp^9a^3q^9 \\\ pt &= tp \\\ qt &= tq \\\ a^{-3}ta^3k &= ka^{-3}ta^3 \end{align}
It is given in D.J. Collins, A simple presentation of a group with unsolvable word problem.