功能更强大的计算机(Turing Machine)能否确定一个问题,而乔姆斯基层次结构中功能较弱的计算机可以很好地解决这个问题

问题描述 投票:1回答:1

对于一组输入字母(a,b),将语言L定义为“所有2016个长度字符串的集合”。

所以,

第一种情况:有限自动机可以通过接受或拒绝它来明确确定输入字母(a,b)上给出的任何输入是否为L,换句话说,它可以确定输入字符串的长度是否为2016?

第二场景:假设我想了解图灵机的工作原理,因此即使从功能较弱的机上获得了答案,我们仍在图灵机上运行该任意字符串。

但是不幸的是,数年过去了,但是图灵机并没有停止运转,也就是说-“对于这种任意输入,它已经陷入了无限循环”。

这个事实令我非常困惑,为什么图灵机比有限的自动机更强大,但无法决定有限的自动机决定了什么

编辑:

示例:L =({M} | M是可接收长度为2015的字符串的图灵机)] >>

[我们知道,如果通过常规语言的棱镜看到上述示例,则长度为2015的语言是有限的,因此它们是常规的。

但是图灵机M的语言L是不确定的,并且可以递归枚举。

或多或少让我感到困惑

对于一组输入字母(a,b),将语言L定义为“所有2016个长度字符串的集合”。因此,第一种情况:有限自动机可以清楚地确定是否有任何输入超出了输入...

automation finite-automata computation-theory turing-machines
1个回答
1
投票

图灵机可以用任何常规语言决定成员资格。我认为您的困惑是TM can

© www.soinside.com 2019 - 2024. All rights reserved.