1

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?

Omari Celestine
  • 1,025
  • 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 02 '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 02 '18 at 12:53

1 Answers1

1

You go about designing such a machine by first developing an algorithm. It may be a good idea to keep in mind the Turing machine's limitations as you think through the agorithm (it can't "look ahead" very well, for intance, so if you manage to keep your working area free of empty characters, that will make it easy to know when you've reached the end), but apart from that, design the algorithm using language, illustrations and notes that you understand and read well. Things like "move that character to the left side of the string", and so on.

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".

And then you can start designing the actual machine instructions.

There are algorithms based entirely on just cleverly reordering the string, and then deleting all the superfluous characters, so you don't have to count the occurrences of each letter on multiple tapes. But you could if you wanted to. If you aleady know how to do that, then that may just as well be a faster machine for you to construct.

Arthur
  • 199,419