对于一组输入字母(a,b),将语言L定义为“所有2016个长度字符串的集合”。
所以,
第一种情况:有限自动机可以通过接受或拒绝它来明确确定输入字母(a,b)上给出的任何输入是否为L,换句话说,它可以确定输入字符串的长度是否为2016?
第二场景:假设我想了解图灵机的工作原理,因此即使从功能较弱的机上获得了答案,我们仍在图灵机上运行该任意字符串。
但是不幸的是,数年过去了,但是图灵机并没有停止运转,也就是说-“对于这种任意输入,它已经陷入了无限循环”。
这个事实令我非常困惑,为什么图灵机比有限的自动机更强大,但无法决定有限的自动机决定了什么
编辑:
示例:L =({M} | M是可接收长度为2015的字符串的图灵机)] >>
[我们知道,如果通过常规语言的棱镜看到上述示例,则长度为2015的语言是有限的,因此它们是常规的。
但是图灵机M的语言L是不确定的,并且可以递归枚举。
或多或少让我感到困惑
对于一组输入字母(a,b),将语言L定义为“所有2016个长度字符串的集合”。因此,第一种情况:有限自动机可以清楚地确定是否有任何输入超出了输入...
图灵机可以用任何常规语言决定成员资格。我认为您的困惑是TM can