I have this problem, where I have an input where:
- alphabet of the input string is Σ = {a,b,c}
- need to add a " " after every 4 characters.
Example: Input = "aabacc", Output = "aab bacc".
I don't really know how to solve this problem since i have to shift all the values many time. Maybe someone has seen a similar problem and can help me a bit?
The problem:
If you work on a TM with only one input/output tape, then you are right. Unfortunately there is no really nice way other than shifting many times (always the remaining suffix after every fourth position). Any approach will imply a lot of running back and forth. The good thing is that you only need to program this loop once for four-symbol groups. So you still have much less work than the TM.
Maybe you also know that additional tapes can be used without changing the computational power. Then you could copy the input string to an auxiliary tape inserting a space every four positions. In the end you then copy the content of the auxiliary tape to the input/output tape.