问题标签 [turing-complete]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 是什么让人们认为 NN 比现有模型具有更强的计算能力？
我在 Wikipedia 中读到，定义在任意实数/有理数字段上的神经网络函数（以及算法模式和推测的“反递归”模型）比我们今天使用的计算机具有更多的计算能力。当然，这是俄罗斯维基百科（ru.wikipedia.org）的一个页面，可能没有得到适当的证明，但这并不是唯一的来源……谣言
现在，我真的不明白的是：字符串重写机（NN 与图灵机一样是字符串重写机；只是编程语言不同）如何比通用的 U 机更强大？
是的，描述性工具确实不同，但事实是此类的任何功能都可以（容易或不容易）变成合法的图灵机。我错了吗？我错过了什么重要的事情吗？
人们这么说的原因是什么？我确实知道不可判定的现象在今天已被广泛接受（尽管根据我所读到的内容并没有得到一致的证明），但我并没有真正看到神经网络能够解决这个特定问题的最小机会。
插件：Not consistently proven according to what I've read- 我的意思是你可能想看看 A. Zenkin（俄罗斯数学家）在 90 年代中期之后的论文，他有说服力地假设 G. Cantor 的概念是错误的，包括超限集、不可数集、对角化方法（图灵用于证明不可判定性的方法）和其他方法。甚至 Goedel 的不完备性定理也仅在 21 世纪以正确的方式被证明。这只是为了将 Zenkin 的工作插入帖子，因为我不知道这些知识在 CS 社区中有多么广泛，所以如果这看起来很愚蠢，请原谅我。
谢谢！
language-agnostic - 如何使用这台图灵机？
这是小程序LogiCell 1.0的屏幕截图，我在这里找到了链接。
如左下角所示，这是求和0+1，结果是01b（右下角）。
我无法将显示的内容与输入和输出相关联。例如在这种情况下 - 查看快照，您如何确定输入是0和1并且输出是01？
latex - 我听说 LaTeX 是图灵完备的。有没有用 LaTeX 编写的程序？
使用通常被认为是排版语言的东西可以做一些有趣的事情。例如，您可以使用 postscript构造 Mandelbrot 集。
在这个 MathOverflow 问题中建议LaTeX 可能是图灵完备的。这意味着编写任意程序的能力（尽管这可能并不容易！）。有谁知道 LaTeX 中此类程序的任何具体示例，它对该语言做了一些非常不寻常的事情？
neural-network - 图灵完备性有多大用处？神经网络图灵完备吗？
在阅读一些关于循环神经网络的图灵完备性的论文时（例如：Turing computability with neural nets，Hava T. Siegelmann 和 Eduardo D. Sontag，1991），我觉得那里给出的证明并不是真的那样实际的。例如，参考论文需要一个神经网络，其神经元活动必须具有无限精确性（以可靠地表示任何有理数）。其他证明需要一个无限大小的神经网络。显然，这并不是那么实际。
但我现在开始怀疑，要求图灵完备是否真的有意义。按照严格的定义，现在没有一个计算机系统是图灵完备的，因为它们都无法模拟无限磁带。
有趣的是，编程语言规范最常将其打开，无论它们是否完整。这一切都归结为他们是否总是能够分配更多内存以及函数调用堆栈大小是否无限的问题。大多数规范并没有真正指定这一点。当然，所有可用的实现都在这里受到限制，因此编程语言的所有实际实现都不是图灵完备的。
因此，您可以说所有计算机系统都与有限状态机一样强大，仅此而已。
这让我想到了一个问题：图灵这个术语到底有多大用处？
回到神经网络：对于神经网络（包括我们自己的大脑）的任何实际实现，它们将无法表示无限数量的状态，即根据图灵完备性的严格定义，它们不是图灵完备的。那么，如果神经网络是图灵完备的，这个问题是否有意义呢？
它们是否与有限状态机一样强大的问题已经在更早的时候得到了回答（Minsky 于 1954 年给出的答案：是的），而且似乎也更容易回答。即，至少在理论上，这已经证明它们与任何计算机一样强大。
其他一些更多关于我真正想知道的问题：
是否有任何理论术语可以更具体地说明计算机的计算能力？（鉴于其有限的内存空间）
您如何将神经网络的实际实现与计算机的计算能力进行比较？（如上所述，图灵完备性没有用。）
c-preprocessor - C99 预处理器图灵完备吗？
在发现Boost 预处理器的功能后，我发现自己想知道：C99 预处理器 Turing 是否完整？
如果没有，不符合资格缺少什么？
sql - 将过程代码展开到 SQL 中
将过程代码转换为 SQL 的行为最近引起了我的兴趣。我知道并不是所有的东西都可以用图灵完备的程序语言来表达。
但是，如果您有特殊用途的程序语言怎么办？例如转换这样的东西：
进入这个：
这样的东西有名字吗？
此外，在我的伪代码中假设它row是不可变的，并且不可能做类似Table[0].FirstName...和其他显然没有（简单）转换为 ANSI SQL 的事情。
谁能给我这个名字？
makefile - makefile 图灵完整吗？
最近在工作中，我一直在做一些从 Makefile 到替代构建系统的翻译。我在某些地方看到了一些使用功能映射、过滤器和 foreach 构造的非常复杂的 Make 代码。这让我感到惊讶，因为我认为构建脚本应该尽可能地具有声明性。
无论如何，这让我想到：Makefile 语言（比如最新的 GNU make 具体来说）图灵是否完整？
programming-languages - 像 Coq 这样的非图灵完备语言的实际限制是什么？
由于那里有非图灵完整的语言，并且鉴于我没有在大学学习 Comp Sci，有人可以解释一下图灵不完整的语言（如Coq）无法做到的事情吗？
还是没有真正的实际兴趣的完整性/不完整性（即在实践中没有太大区别）？
编辑-我正在寻找一个答案，由于 X 或类似的原因，您无法用非图灵完备的语言构建哈希表！