I'm trying to understand the following proof of the unsolvability of the word problem in semigroups. I tried to reproduce the proof from some kind of personal communication, so I'm not sure everything is very precise/correct, and I have some questions about it (they are at the end).
First, some notation. We say that the Turing machine with tape alphabet $\{a_1,\dots, a_n\}$ and set of states $\{q_0,\dots,q_m\}$ ($q_1$ is the initial state, $q_0$ is the terminal state) is in configuration $AqxB$ if the machine is in state $q$, its head points at the cell with the symbol $x$, and to the left of that cell is the word $A$, to the right of that cell is word $B$.
An instruction of the form $q_ia_j\to q_ra_sR$ results in the following change of configuration: $Aq_ia_j\to Aa_sq_r(bB')$ where $bB'$ is the word $B$ with the first letter "separated" from the remainder of the word. Similarly, if we have an instruction like $q_ia_k\to q_ra_sL$, then the configuration changes as follows: $Aq_ia_jB\to A'q_raa_sB$ where $A=A'a$.
Now the proof. We construct the following semigroup.
Generators: $a_1,\dots,a_n,q_1,\dots,q_m, \lhd, \rhd$
Relations (in orange boxes):
Claim. $q_1X=q_0$ iff the machine halts on input $X$.
Suppose the machine halts on $X$. So the initial configuration is $q_1(xX')$ where $X=xX'$ (or $q_1X$ for short). To every configuration, there corresponds a word. If one configuration changes to another, then the corresponding words are equal (here we're using the relations in the first four boxes, I guess). Suppose the machine halts in configuration $Aq_0a_jA'$ where $A,A'$ are some words. Then we can successively apply the relations from the last box and the result will be $q_0$ (the empty tape, and the head points to some empty cell). Since there is a chain of equalities verifying that $q_1X$ equals $q_0$, this implication is proved.
Conversely, suppose $q_1X=q_0$. If we knew that the chain of equalities witnessing $q_1X=q_0$ only uses the relations "from left to right", then this would correspond to the run of the machine on input $X$ and eventually halting. So it suffices to prove that there is such a chain. Consider the shortest chain witnessing $q_1X=q_0$. We show that it cannot have instances of "right-to-left" applications of the relations. Assume the converse. Consider the last such instance of "right-to-left" application. For example, consider the relation in the first box above. Then $Pa_sq_ra_kQ=Pq_ia_ja_kQ$. The next instance of the application of relations must be "left-to-right": $Pq_ia_ja_kQ=Pa_sq_ra_kQ$. In sum, we have $Pa_sq_ra_kQ=Pq_ia_ja_kQ=Pa_sq_ra_kQ$, which is "trivial", so it can be thrown away from the chain. This contradicts to the minimality of the chain.
First, why do we need to add these $\lhd, \rhd$ in the list of generators (and the corresponding relations)? For example, what bad would have happened if we replaced the relation from the second box, namely $q_ia_j\lhd=a_sq_r\#\lhd$, to just $q_ia_j=a_sq_r$ or $q_ia_j\#=a_sq_r\#$? Why do we need to signify that nothing will ever appear to the right (except $\#$)? A specific example of something bad happening would be great, as I didn't understand "in general terms" why we need these.
Second, in the last paragraph, after we considered the last instance of "right-to-left" application of the relations, why is the next application of the relation $Pq_ia_ja_kQ=Pa_sq_ra_kQ$? I understand that it must be "left-to-right", but why are we applying exactly this relation? If we applied some other "left-to-right" relation instead, then we wouldn't get the trivial relation anymore.
Also, general comments, edits, or suggestions about this proof are welcome too.
Firstly an inconsistency -- you swap the meanings of $q_0$ and $q_1$ relative to initial and final states. The meaning consistent with the drawing (presumably the most difficut bit to edit) is that $q_0$ is the final state, which means the error is in the first quoted paragraph, and what is written after the drawing is correct.
Regarding your first question, if we take your suggestion of $q_{i}a_{j}=a_{s}q_{r}$, then we would have to add an extra relation interpreting the action performed when we are in state $q_{r}$ and reading the blank symbol: that is, if there is a instruction $q_r\#\to q_ta_kR$ we need a relation $q_r=a_kq_t$ (and a corresponding relation if our instruction moves left). So that's a bit of a non-starter; the change we had made would mean we'd have to write down two more relations in any case.
Likewise, if we take your suggestion of $q_ia_j\#=a_sq_r\#$, we would again need an extra relation interpreting the possibility that we will move right when $q_r$ reads the blank symbol, as this would requre us to rustle up an additional blank symbol that isn't currently present in our word, so it wouldn't be covered by any of the possibilities we already have written down. That is, if there is a instruction $q_r\#\to q_ta_kR$ we need a relation $q_r\#=a_kq_t\#$. So for us, the symbol $\lhd$ manages to play the role of an infinitely inexhaustible supply of blank symbols; when we encounter it we pop one off the front, and keep the remaining infinitely many remaining condensed into the one symbol (since of course we cannot write the infinitely many symbols down). The way it is written allows us to deal with the special behaviour of "the last symbol on the tape" in a succint way.
Now regarding your second question, I guess the missing observation here is that, as no relation increases the number of $q$-terms that appear, we know there is no other $q_t$ appearing anywhere in our word except for the single $q_i$ we're interested in. Then furthermore as we know there is a instruction $q_ia_j\to q_ra_sR$, we know there is no other instruction $q_ia_j\to\text{anything}$, and furthermore we make only left-to-right applications by assumption. So the only relation that can apply is the one that undoes what we just did.
The only other thing for a general comment, edit or suggestion is what happens if the instruction for $q_1x$ (where $X=xX'$) tells you to move left. You could of course use $\rhd q_1X$ instead ;)