# Turing Machine that orders the alphabet/characters of the entered string based on the frequency of each symbol

Give the following problem:

Design a Turing Machine such that given string from the alphabet $\{a, b, c, d\}$, produces on the tape a combination of the string "abcd" in which each symbol occupies the position coresponding to the relative order of it's absolute frequency in the entered/given string. The combination is to be displayed in descending order. In the case of coinciding frequencies, the symbols are to be located in inversed order of appearance en the entry string. For example, the string $\underline{\triangle} a b a d c d a b c a a \triangle \triangle ...$ must produce the output $\underline{\triangle} a c d b \triangle \triangle ...$

Note:

The $\triangle$ represents an "empty" character and _ the position of the reading head.

I have not encountered any problems related to this so I am not sure to proceed.

But if I am correct, I would need to use the counting Turing Machine and possibly a programming technique such as multiple tapes. Would that be necessary?

How do I go about designing such a machine?

• Does $\triangle$ denote a fifth letter of your Turing machine's alphabet (an "empty" character, or a zero, if you will)? And does $\underline{\phantom{\triangle}}$ mean that's where the reading head is? Also, multiple tapes is never necessary (it doesn't make a Turing machine more complete), but not having to worry about different countings being in the way of one another is definitely a plus. – Arthur Aug 2 '18 at 12:49
• @arthur Sorry for lack of those details. The $\triangle$ represents an "empty" character and _ the position of the reading head. I will update the question to include this. – Omari Celestine Aug 2 '18 at 12:53

Once you've done that, you can expand on that algorithm with details on what operations your machine will actually be doing during each step and what internal states it will have. For instance, "the first character of the string is an $a$, it saves that as an internal state" and "it keeps swapping this character with its left neighbour until it it reaches an empty character".