有一种图灵机可以处理的语言,LBA不能,但有没有任何有用的实际问题,LBA无法解决,但TM可以解决？
LBA只是一台带有限磁带的图灵机器,实际的计算机存储空间有限,所以在我看来LBA无法做到的实际重要性. 除了线性有界自动机不仅仅是一个有限的磁带,而是一个大小与输入大小成线性函数的磁带这一事实.有限性的线性是否以某种方式限制了LBA？
是否存在LBA无法应对的问题,但是指数有界自动机可能(如果存在这样的话)？
我研究了基础图灵机理论作为本科生.我从来没有见过任何定时图灵机.一个例子:图灵机,计算自启动以来经过的秒数.
现代计算机显然有能力做到这一点.因此,计算机的功能是图灵机可以做的超集.这里有一些文章/数学/文献吗？或者在某些方面我的论点是错的？
我想知道递归和递归可枚举语言之间的区别在于停止和图灵机.我知道递归可枚举语言是递归语言的一个子集,但我不确定除此之外的差异.
theory computer-science turing-machines computation-theory formal-languages
在下面的语言大号不可判定？
L = { M | M是图灵机描述,并且存在长度为k的输入x,使得M在最多k步之后停止}
我想是的但是我无法证明这一点.我试着想到减少停止问题.
我现在正在学习计算理论课程.我能很好地理解这些概念.我能够解决问题.而且,当我向我的导师询问真实世界的应用程序时,他告诉我这些概念在编译器设计中肯定是有用且必不可少的.但是,至少要做一个有意义的研究,我需要一些解释,如何在编码中使用这些概念.
例如,如果我想设计自己的grep.我将在C中使用字符串函数.我不知道如何在编码中使用正则表达式.
同样的情况适用于图灵机.
如果我想添加两个数字,为什么我必须遵循这些一元的概念.硬件是否实现了这些概念？
我需要帮助设计一台计算以下内容的图灵机f(x,y) = x*y mod 4.如何处理二进制基地这个问题,在$x$和$y$有两位？
有了DFA图,我怎样才能将它转换为图灵机？我是否必须找到DFA接受的语言然后创建图灵机？或者有直接的方法吗？
谢谢.
因此，我尝试搜索语言的精确定义，但是所有文章都假定该定义对每个人都是显而易见的。显然，对我来说不是。Turing机器语言的解释是什么？
我想知道如何使用带有单磁带的确定性图灵机计算函数A mod B ，其中 A > B 和 A, B 是一元数。
谢谢
图灵机的定义说，禁止人们阅读/修改其指令表（程序）。确实，图灵机无法访问其自己的程序。
如果可以弱化这一限制，可以获得什么好处？如果机器可以分析和/或修改其程序。这会扩展图灵计算任务的类别吗？