图灵机的构建决策者而不是决策者

Question

如何制作一个图灵机图形，它可以识别all words with an even number of a's，但它是not a decider而不是其他任何东西。另外，如何为相同的语言制作decider图灵机图形。

Answer 1

所有具有偶数个a的单词的语言都是一种常规语言，因此一个简单的双态DFA就可以接受这种语言。同一台机器是一个双态判决器TM，碰巧除了读取输入之外，它不使用磁带做任何事情。

要将这样的判定器转变为识别器-非判定器(因为所有判定器也都是识别器)，我们必须让TM显式地识别具有奇数个a的字符串，而不是简单地停止-拒绝，进入无限循环。这可以很容易地通过一个状态来完成。