我正在学习一项离散数学测试,我们正在学习乔姆斯基的层次结构和识别层次结构各个层次的自动机类型.我被教导说大多数计算机语言属于层次结构的"2级和1级",但不是精确的.
我的问题是:
每个级别有哪些功能？
这不过是理论基础吗？我想知道Dennis Ritchie和James Gosling这样的语言设计师在设计C和Java时是否需要考虑这些因素.他们呢？怎么会有人申请这个？
我们被告知图灵机器识别层次结构的0级.如果是这样,是否有任何属于0级的语言功能？我猜这可能是自然语言处理,是吗？
theory language-design automata turing-machines chomsky-hierarchy
这些天我一直在研究NP问题,计算复杂性和理论.我相信我终于掌握了图灵机的概念,但我有一些疑惑.
我可以接受一个非确定性的图灵机有几个选项,可以为给定的状态和符号读取做什么,它总是会选择最佳选项,如维基百科所述
NTM如何"知道"它应该采取哪些行动？有两种方式可以看待它.一个是说机器是"最幸运的猜测者"; 如果存在这样的转变,它总会选择最终导致接受状态的过渡.另一种是想象机器"分支"成许多副本,每个副本都遵循一个可能的过渡.虽然DTM具有它遵循的单个"计算路径",但NTM具有"计算树".如果树的任何分支以"接受"条件停止,我们说NTM接受输入.
我无法理解的是,既然这是一个虚构的机器,我们从多数时间内解决NP问题得到什么呢？我的意思是,我还可以理解一个解决O(1)中NP问题的神奇机器,如果它可能永远不会存在,我会从中获得什么？
提前致谢.
我正在阅读" 计算复杂性:现代方法"这本书,我在理解不经意的图灵机时遇到了问题.
不经意的图灵机(TM)是这样的TM,其头部的移动完全由输入的长度决定.也就是说,TM没有注意到它的输入.到现在为止还挺好.
但其中一个练习是证明以下定理:
If a language L is decidable in time T(n)
then there exists an oblivious TM that decides L in time O(T(n)^2).
很明显,不可思议的TM不能在原始输入上操作,L而是在某些编码版本上操作.即,定理的主旨是编码一个的比特串到整数(在不经意TM的输入的长度).但是如果想要将L(位串)的可能输入集合编码为整数,则由于存在2^n长度的位串,因此会很快地遇到非常高的数字n.
我能正确理解问题吗？你如何证明这个定理？
AFAIK,可计算的数字是数字,其第i个索引可以由图灵机返回.因此,一个不可计算的数字就像一个数字,如果某个其他程序在某些其他输入上停止,则会确定其小数点,等等.但是,再次,PI是一个实数,不能由TM枚举,因此,不能计算？那么哪个学派是正确的？
对于例如,图灵机的不接受自己的编码语言不能被任何图灵机接受.
在维基百科文章的Prolog包括该图灵机模拟器:
turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
symbol(Rs0, Sym, RsRest),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, …有一种图灵机可以处理的语言,LBA不能,但有没有任何有用的实际问题,LBA无法解决,但TM可以解决？
LBA只是一台带有限磁带的图灵机器,实际的计算机存储空间有限,所以在我看来LBA无法做到的实际重要性. 除了线性有界自动机不仅仅是一个有限的磁带,而是一个大小与输入大小成线性函数的磁带这一事实.有限性的线性是否以某种方式限制了LBA？
是否存在LBA无法应对的问题,但是指数有界自动机可能(如果存在这样的话)？
我研究了基础图灵机理论作为本科生.我从来没有见过任何定时图灵机.一个例子:图灵机,计算自启动以来经过的秒数.
现代计算机显然有能力做到这一点.因此,计算机的功能是图灵机可以做的超集.这里有一些文章/数学/文献吗？或者在某些方面我的论点是错的？
我想知道递归和递归可枚举语言之间的区别在于停止和图灵机.我知道递归可枚举语言是递归语言的一个子集,但我不确定除此之外的差异.
theory computer-science turing-machines computation-theory formal-languages