图灵机辅助

Question

我一直在设计图灵机，我最近解决的是一种语言L = {w：na（w）= nb（w）}，其中w中的a的数量等于b的数量在w。

但是，我如何为一种语言设计图灵机，其中w的数量不等于w的b数？ （例如，L = {w：na（w）≠nb（w）}？

我一直用来参考的书和网站定义了图灵机如下：

M =（Q，Σ，Γ，δ，q0，☐，F），其中Q是状态，Σ是输入字母，Γ是磁带字母，δ是转换，q0是开始状态，☐是a作为Γ（☐εΓ）元素的空白空间，F是指定为qf的最终状态。

Answer 1

如果你最近解决了a和b的数量相等的情况，对于它们不相等的情况的立即解决方案是这样的：

• 如果你曾经崩溃（没有有效的转换），那么改为转换为halt_accept;
• 如果您曾经通过转到halt_reject明确拒绝，请转到halt_accept;
• 如果您曾经通过输入halt_accept接受，请转到halt_reject。

这个新的TM（1）接受你的TM在a和b的数量相等的情况下不会被接受的任何东西，并且（2）拒绝你的TM在相同数量的情况下接受的任何东西。和b。

事实上，这个程序适用于任何TM，其工作只是决定用机器语言输入字符串的成员资格;在补充语言中枚举字符串是行不通的，但这不一定是你需要的东西（并且你可以通过使用像这样构造的机器作为枚举所有字符串并检查它们的另一个子机器来获得枚举）。