5

我在 Wikipedia 中读到，定义在任意实数/有理数字段上的神经网络函数（以及算法模式和推测的“反递归”模型）比我们今天使用的计算机具有更多的计算能力。当然，这是俄罗斯维基百科（ru.wikipedia.org）的一个页面，可能没有得到适当的证明，但这并不是唯一的来源……谣言

现在，我真的不明白的是：字符串重写机（NN 与图灵机一样是字符串重写机；只是编程语言不同）如何比通用的 U 机更强大？

是的，描述性工具确实不同，但事实是此类的任何功能都可以（容易或不容易）变成合法的图灵机。我错了吗？我错过了什么重要的事情吗？

人们这么说的原因是什么？我确实知道不可判定的现象在今天已被广泛接受（尽管根据我所读到的内容并没有得到一致的证明），但我并没有真正看到神经网络能够解决这个特定问题的最小机会。

插件：Not consistently proven according to what I've read- 我的意思是你可能想看看 A. Zenkin（俄罗斯数学家）在 90 年代中期之后的论文，他有说服力地假设 G. Cantor 的概念是错误的，包括超限集、不可数集、对角化方法（图灵用于证明不可判定性的方法）和其他方法。甚至 Goedel 的不完备性定理也仅在 21 世纪以正确的方式被证明。这只是为了将 Zenkin 的工作插入帖子，因为我不知道这些知识在 CS 社区中有多么广泛，所以如果这看起来很愚蠢，请原谅我。

谢谢！

4

5 回答 5

3

根据我所做的少量研究，这些关于跨图灵系统或康托尔对角化证明的不正确性等的大多数主张，容我们说，在合法的数学界是“有争议的”。像“曲柄”这样的词经常被抛出。

显然，强大的 Church-Turing 论文仍未得到证实，但正如您所指出的，确实没有充分的理由相信人工神经网络构成了超出一般递归/UTM/lambda 演算/等的计算能力。

于 2010-05-10T16:43:38.193 回答
2

从理论的角度来看，我认为你是绝对正确的——神经网络提供的新的或不同的东西很少。

从实际的角度来看，神经网络只是一种将解决方案转换为自然且容易并行执行的形式的方法，而图灵机本质上是顺序的，并行执行它们的序列相对困难。事实上，过去几十年在 CPU 开发中所做的大部分工作基本上都是在找出并行执行代码的方法，同时保持它按顺序执行的错觉。现代 CPU 中的许多硬件都致力于维持这种错觉，而并行执行变得明确的程度主要是承认维持这种错觉已经变得非常昂贵。

于 2010-05-10T16:56:24.943 回答
1

从外行的角度，我看到

  • NN 在解决某些类型的问题方面可能比图灵机更有效，但它们在计算上并没有更强大。
  • 即使 NN 被证明比 TM 更强大，在当前硬件上执行也会使它们变得不那么强大，因为当前硬件只是 TM 的近似值，并且只能执行可由有界 TM 计算的问题。
于 2010-05-17T19:24:16.747 回答
1

任何“证明”康托尔的对角线方法不起作用的人只能证明他们自己的无能。参照。威尔弗雷德·霍奇斯（Wilfred Hodges）的一位编辑回忆了一些绝望的论文，对这些尝试出了什么问题做出了令人惊讶的同情解释。

您可以提供对超图灵神经网络的推测性描述，就像您可以提供对其他类型的超图灵计算机的推测性描述一样：超计算是可能的想法并没有什么不连贯的，并且已经对机械超级计算机进行了推测性描述，其中超级计算机被规定有无限精细的雕刻，为停机机器编码一个预言：这种机器的存在符合牛顿力学，尽管不是量子力学。相反，Church-Turing 论点说它们不能被构建，并且有两个理由相信 Church-Turing 论点是正确的：

  1. 从来没有制造过这样的机器。和
  2. 已经完成了将物理模型与计算模型联系起来的工作，Robin Gandy 在 1970 年代早期开始工作，最近还有 David Deutsch 等人的工作（例如，机器、逻辑和量子物理以及 John Tucker（例如，计算通过运动系统实验），它认为物理学不支持超计算。

主要的一点是，Church-Turing 命题的真实性是一个经验事实，而不是一个数学事实。这是一个我们可以有信心的是真实的，但不是确定性的。

于 2010-05-18T10:07:16.000 回答
1

您可能对 S. Franklin 和 M. Garzon 的神经可计算性感兴趣。谷歌上有一个预览。它讨论了神经网络的计算能力，并指出有传言说神经网络比图灵机更强大。

于 2010-06-07T16:12:45.133 回答