Голландский национальный флаг на машине Тьюринга

Question

У меня есть последовательность символов xxxxxx (с x ^ k и k> 0) Моя цель - превратить это предложение в голландский флаг, то есть:

xxxxx -> RRWWBB хххх -> RWBB

с R <= W <= B </p>

Все решения, которые я нашел, имеют очень высокую сложность. Есть ли у вас какие-либо подсказки / подсказки, чтобы помочь мне построить машину Тьюринга, используя только одну ленту и одну головку / курсор?

Answer 1

Как насчет разделения задачи на подзадачи, например:

1. Измените последний X на B.
2. Измените последний X на W.
3. Измените первый X на R.
4. Измените BW на WB.

РЕДАКТИРОВАТЬ:

Вот другой подход: вы говорите, что видели алгоритмы, которые начинаются с присутствующих цветов (не по порядку).Так что все, что вам действительно нужно, это способ расставить цвета (не по порядку) ...