"图灵完成"的含义是什么意思？
你可以给出一个简单的解释,而不会涉及太多的理论细节吗？
据我所知,CSS不是图灵完整的.但我对CSS的了解非常有限.
用通常被认为是排版语言的东西做一些有趣的事情是可能的.例如,您可以使用postscript构造Mandelbrot集.
在此MathOverflow问题中建议LaTeX可能是图灵完备的.这意味着能够编写任意程序(虽然这可能并不容易!).有没有人知道LaTeX中这样一个程序的任何具体例子,它使用该语言做了一些非常不寻常的事情？
在发现Boost预处理器的功能后,我发现自己在想:C99预处理器Turing是否完整？
如果没有,缺少什么不符合资格？
因为那里有非图灵完整的语言,并且鉴于我没有在大学学习Comp Sci,有人可以解释一下Turing-incomplete语言(如Coq)不能做的事情吗？
或者是没有实际利益的完整性/不完整性(即它在实践中没有太大的区别)？
编辑 - 我正在寻找一个答案,你不能用非Turing完整语言构建一个哈希表,因为X或类似的东西!
programming-languages functional-programming turing-complete coq
有人声称Scala的类型系统是图灵完整的.我的问题是:
这有正式的证据吗？
如何在Scala类型系统中进行简单的计算？
这对Scala有什么好处 - 语言？这是否使Scala在某种程度上比没有图灵完整类型系统的语言更"强大"？
我想这通常适用于语言和类型系统.
我最近在阅读关于人工生命的文章,并且发表了声明,"康威的生命游戏展示了足够的复杂性,被归类为通用机器." 我只是粗略地了解通用机器是什么,维基百科只让我接近理解,就像维基百科一样.我想知道是否有人可以对这个非常性感的陈述有所了解？
对我而言,康威的"生命游戏"似乎是一种可爱的分心,带来了一些巨大的影响:我无法在那和计算器之间实现飞跃？这甚至是我应该做的飞跃吗？
在阅读一些关于递归神经网络的图灵完整性的论文时(例如:使用神经网络进行图灵可计算性,Hava T. Siegelmann和Eduardo D. Sontag,1991),我感觉到那里给出的证据并不是真的那样实际的.例如,参考文献需要神经网络,神经元活动必须具有无限精确性(可靠地表示任何有理数).其他证明需要无限大小的神经网络.显然,这并不是那么实用.
但是我开始怀疑现在是否真的有意义要求图灵的完整性.根据严格的定义,现在没有计算机系统是图灵完整的,因为它们都不能模拟无限的磁带.
有趣的是,如果编程语言规范完整或不完整,那么编程语言规范最常开放.这一切归结为问题,如果它们总是能够分配更多的内存,并且函数调用堆栈大小是无限的.大多数规范并没有真正指定这一点.当然,所有可用的实现都受到限制,因此编程语言的所有实际实现都不是图灵完整的.
所以,你可以说是所有计算机系统都和有限状态机一样强大而不是更多.
这让我想到了这样一个问题:图灵这个词完全有用吗？
回到神经网络:对于神经网络(包括我们自己的大脑)的任何实际实现,它们将无法表示无限数量的状态,即通过严格定义图灵完整性,它们不是图灵完整的.那么神经网络图灵完全是否有意义的问题呢？
他们是否像有限状态机一样强大的问题早已得到了回答(1954年由明斯基回答,答案当然是肯定的)并且似乎也更容易回答.即,至少在理论上,这已经证明它们和任何计算机一样强大.
其他一些问题更多的是我真正想知道的:
是否有任何理论术语可以说明计算机的计算能力？(鉴于其有限的存储空间)
你怎么能比较神经网络的实际实现与计算机的计算能力？(如上所述,图灵完整性没有用.)
finite-automata state-machine turing-complete neural-network