Consider the alphabet $\{0,1\}$. A word is a finite sequence of letters. A word is called basic if it's of one of the following forms: $1^k0, 1^k00, 1^k000,1^k0000,1^k00000$; where $1^k=11\dots11$ ($k$ times). A word is called good if it's a finite sequence of basic words. So for example the word $10111000110000$ is good but the words $1,1111, 0,000,01,1000000$ are not good. A good word must start with $1$, end with $0$, and it cannot contain more than five $0$s in a row in it.
I've been trying to come up with a program for a register machine that accepts a word in register 1 and, if the word is good, it gives 1 in register 1; otherwise it gives 0 in register 1.
The syntax is as follows:
- add1 reg - Append "1" onto register 'reg'
- add0 reg - Append "0" onto register 'reg'
- jump n - Jump forward by 'n' instructions
- jumpb n - Jump backward by 'n' instructions
- case n - perform a case operation on register number n
- goto name - Jump to line identified by 'name'
- label name - Identifies a line as 'name'
"case n" works as follows.
If register n is empty, we go to the very next instruction.
If the first symbol of register n is 1, we delete that symbol and go to the second instruction after the case instruction.
If the first symbol of register n is 0, we delete that symbol and go to the third instruction after the case instruction.
I only have some idea how to partially implement this. For example let's how we can account for the case when more than five $0$s are followed by $1$ (in which case the word is not good). Perform cases on register 1.
If it's empty, append 1 to register 1 and end the program.
If the first symbol in register 1 is 0, then add 1 to register 2.
If the first symbol is 1, we add 111111 to register 3 and compare it with what is written in register 2. If registers 2 and 3 have same stuff in it, then this means that the word on which the program is running is not good (it contains more than 5 zeros in a row).
This is just some idea but of course it's incomplete and I don't know how to account for other cases. Even if there were no other cases, the program corresponding to this idea needs modifications.
I've never worked with register machines before, but I think the following is a quick and dirty way of doing this, using only a single register. Let me know if I've made any errors.