Hel*_*nar 4 theory mapping state-machine turing-machines
我一直在努力寻找这个理论问题的答案,即使它不是一个直接的编程问题,我相信它确实是相关的.
假设一种不能超过1000个方格的图灵机.这种类型的可识别语言集与正常可识别语言集之间的关系是什么.
如果我正确地理解你的问题,那么你所说的Turing-like机器的磁带只限于最终字母表中的一些常量legnth(在你的问题1000中).磁带的长度不依赖于输入大小(线性有界自动机的情况).
在这种情况下,磁带可以表示的状态数是不变的.更具体地说,如果磁带的长度是T并且字母表的大小是A,那么磁带只能编码A T状态.
另外,图灵机有一些内部状态(假设这些状态的数量是S).在每个点上,机器都有一些内部状态和一些磁带状态,因此我们可以使用普通的有限状态机模拟具有恒定长度磁带的图灵机.
要构建有限状态机,您需要采用有限图灵机的所有可能状态.这是机器的内部状态(它们有S)和磁带的状态(它们的A T)的组合,因此最终得到具有S*A T状态的有限状态机.这是相当多的,但我们在理论上并不关心它 - 它是一个常数.
所以,我的答案是你的有限的恒定磁带图灵机可以识别与finitie-state机器相同的语言.