在图灵机的荷兰国旗 [英] Dutch national flag on a Turing Machine

问题描述

我有个字符XXXXXX序列（其中x ^ k和K> 0） 我的目标是把这个句子译成荷兰标志，即：

I have a sequence of characters xxxxxx (with x^k and k > 0) My goal is to transform this sentence into a dutch flag, that is to say :

为XXXXX - > RRWWBB XXXX - > RWBB

xxxxx -> RRWWBB xxxx -> RWBB

与R＆LT; = W＆LT; = B

with R <= W <= B

这是我发现所有的解决方案，具有非常高的复杂性。 你有任何提示/线索，以帮助我建立一个图灵机只用一盘磁带和一个头/光标？

All solutions that I have found, have a very high complexity. Do you have any hint/clue to help to me build a Turing machine using only one tape and one head/cursor?

推荐答案

如何划分任务为子任务，如：

How about dividing the task into subtasks like:

1. 更改最近X为B.
2. 更改最近X为W.
3. 更改第一个X为R.
4. 更改BW世行。

1. Change the last X to B.
2. Change the last X to W.
3. Change the first X to R.
4. Change BW to WB.

编辑：

下面是另一种方法：你说你见过的颜色present启动（乱序）算法。所以，你真正需要的是一种能够把颜色（乱序）...

Here's another approach: you say you've seen algorithms that start with the colors present (out of order). So all you really need is a way to put the colors in (out of order)...

这篇关于在图灵机的荷兰国旗的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！