擦除其输入的图灵机

Question

我有这个问题： 考虑一个图灵机 Cw，它擦除其输入，在磁带上写入 w，并在扫描 w 最左边的字符时停止。设计图灵机 C011

我需要解释实际问题是什么以及 Cw 的作用。我有点理解它在收到的每个输入上都写了空符号，但其余的我不清楚。希望有人能帮助我理解这个问题以及我需要做什么。

Answer 1

在你的情况下w = 011。

确实，TM 应首先覆盖整个输入。我认为我们可以假设输入没有间隙。因此，一旦 TM 读取输入磁带上的空白区域，它就应该开始写入 011。

写入第二个1时，进入不存在任何转换的状态。这样您就可以确保机器停在该位置。没有明确说明该状态是否应该接受，但将其作为唯一的接受状态是有意义的。

Answer 2

接受的答案解释正确。但是，因为您需要将头部放在最左边的角色上，如下所示：

0 1 1
^

...这三个字从右向左写是有意义的。

一些假设：

• 输入内容不包含空格
• 输入语言为{0,1}。可能不止于此，但转换表应该包含它们的转换，或者具有包罗万象的可能性。
• TM 的头部从属于输入一部分的字符开始。通常假设 TM 从最左边的输入字符开始，但我们可以稍微放松这一要求，首先搜索输入的开头（如果有）。

这里是一个转换表，它清除输入，然后从右向左写入三个字符

011

，并在

0

处停止：

createTuring({
    transitions: [
        { state: "start",    read: "01",             move: "L", nextState: "start"  },
        { state: "start",    read: "_",              move: "R", nextState: "clear"  },
        { state: "clear",    read: "01", write: "_", move: "R", nextState: "clear"  },
        { state: "clear",    read: "_",              move: "L", nextState: "put011" },
        { state: "put011",   read: "_",  write: "1", move: "L", nextState: "put01"  },
        { state: "put01",    read: "_",  write: "1", move: "L", nextState: "put0"   },
        { state: "put0",     read: "_",  write: "0", move: "L", nextState: "back"   },
        { state: "back",     read: "_",              move: "R", nextState: "halt"   },
    ],
    initState: "start",
    tape: "010100111",
});

<script src="https://trincot.github.io/turing.js"></script>

请注意，如果 TM 支持不移动头部的转换，那么您可以省略

back

状态，并在不移动头部的情况下将

put0

状态转换到

halt

。