Search code examples
mathcomputation-theoryturing-machines

What does the fancy R symbol mean as written here?


This is an assigned question I have, and I'm not sure how to interpret the R-like symbol in the exponent position. Does it mean the Turing machine should accept variable numbers of repetitions of w?

Fancy R


Solution

  • The notation wR probably means “w reversed.” The problem most likely asks that the Turing machine shall, if it starts with a word w on its tape, append a # and then w reversed. Afterwards, it shall accept (i.e. terminate). For instance, if the tape contains example in the beginning, it should contain example#elpmaxe after the Turing machine ran.