0

I'm reading the chapter "Fixed Point Puzzles" and there is a problem titled "An Open Problem" after problem #18. The chapter introduces a machine which operates on strings of upper case letters, which are then processed according to some internal rules, and a new string is output. The rules are as follows (so far anyway):

Given a input string, let's call it x, the output is a string, lets call it y. x->y means x outputs y.

  • RULE Q: Given string x, the output of Qx is x. Qx->x

  • RULE C: Given string x which outputs string y, x->y, Cx outputs yQy: Cx-yQy

  • RULE R: Given string x which outputs string y, Rx outputs yy. Rx->yy

  • RULE V: Given string x, Vx outputs the reverse of y.

Now the problem states: Is there such a string x that the output is xA, where A is simply a letter? Can we prove this to be true or false?

My question is, does this problem have a name? Has it been solved? I do believe I have shown it to be false, but perhaps it is a simple problem >_>

user2932481
  • 1
  • 1
    Could you clarify the rules? 1) In Rule C, what does it mean that "string x outputs string y"? 2) Again in Rule C, how should we apply Q? According to the previous line, Qy outputs y, so is yQy just yy? 3) In Rule R, what is y? 4) In Rule V, what is y? – Théophile Apr 26 '19 at 15:53
  • Sorry, I wasn't sure if the problem would be recognisable from a brief description. – user2932481 Apr 26 '19 at 16:10
  • 1
    It's okay if the description is brief so long as it makes sense! – Théophile Apr 26 '19 at 16:12
  • 1
    So Rule C: if you have a string x, if you feed it to the machine, it outputs string y. So given a string like CQA the output would be AQA, since QA outputs A, and C makes it into AQA. The y's in rules R and V are the outputs if you input x, same as for C. – user2932481 Apr 26 '19 at 16:13

0 Answers0