通用模拟计算需要什么？
https://cs.stackexchange.com/questions/1292
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
需要执行什么操作才能执行任何任意 模拟计算？加法，减法，乘法和除法是否足够？
另外，有人确切地知道使用模拟计算可以解决哪些问题，但与数字计算相关？
解决方案
不幸的是，模拟计算中没有“通用”普遍性概念。但是，这篇论文由 Delvenne 提出了对离散（例如图灵机）和连续（例如微分方程）动态系统的普遍性的统一形式主义，并回顾了文献中研究的一些通用系统。这是本文的摘录，该论文非正式地描述了证明动态系统普遍性的程序：
但是，在数学和物理学上研究的大多数动态系统都具有无法计数的状态空间，例如蜂窝自动机，微分方程，分段线性图等。这些系统的示例已被证明是通用的。他们的停止问题是通过以下方式从图灵机中模仿的。我们选择一个特定的最初状态家庭，最终状态的可数家族或最终状态。然后给出停止问题的初始状态和最终状态/一组状态，从初始状态开始的轨迹是否将达到最终状态/一组状态。第7节中给出了更具体的示例。
Jean-Charles Delvenne，什么是通用计算机？，应用数学与计算，第215卷，第4期，2009年10月15日，第1368-1374页
其他提示
我认为除非我们对正在谈论的哪种计算有一个定义，否则我不会回答这个问题。
机器模型WRT的通用性一类ComputationW意味着该类中的任何计算都可以由机器计算。除非您定义“任意模拟计算”类，否则我们无法回答什么是通用性WRT。
现在，您列出的功能只会为您提供多项式及其商，这是一个很小的实际功能，您甚至无法计算简单功能，例如$ 2^x $，$ lfloor x rfloor $，$ sqrt x $ ， ... 使用它们。
如果您的问题是从初始状态开始的物理系统是否会在一段时间内到达另一个状态，并且如果总是可以计算，那么答案取决于我们在谈论的物理类型，以及设置的含义初始配置并观察结果等。
如果我们只是在数学上谈论经典物理（我们可以将任何初始配置设置为无限的精度，而无需考虑设置配置所需的能量之类的事情，并且从数学的角度来看，结果同样是同样的）。长期以来，关于可计算函数的微分方程的解决方案无法计算，请参见Marian B. Pour-el和J. Ian Richards，“”分析和物理学的计算性", 1989.
一个有趣的情况是 N体问题 是可以计算的（如果我没记错的话，答案是否定的，至少对于$ n> 4 $）。
通常，如果我们只能检查两个实数的平等，而两个实数的函数不是连续的WRT典型信息的典型信息类型，因此无法通过Turing Machine计算，因为任何功能（包括较高类型的功能），Turing Machine可以计算是连续的（信息的拓扑结构）。
tl; dr： 如果通过“模拟计算机”，则是指 差分分析仪, ，答案是加法器，恒定单位和集成器。 Bournez，Campagnolo，Graça和Hainry在2006年展出（付费 / 免费重印） 理想化的模型 其中允许在框架中计算所有可计算功能 可计算分析, ，并且该模型只需要这三种单元。
先验功能
您提出的一组操作（加法，乘法，减法和除法），即使是根据root方程完成的，根据定义不足以计算任何 先验功能. 。先验功能包括非常常见的功能，例如$ sin $，$ exp $，$ log $。但是，如下所述，一些模拟计算机模型允许计算超验功能，并且基本上都是图灵机可以计算的实际功能。
模拟计算模型
正如其他人所强调的那样，对于模拟计算机而言，“通用计算”的概念不如标准计算机，在不同的计算机中，在不同的计算模型中，自然的可计算性概念在1930年代相同（请参阅参见 Wikipedia页面上的教堂图灵论文有关详细信息).
为了定义这样的普遍性，应该首先定义模拟计算的良好模型，这是一项艰巨的任务，因为该模型应该是理想化和自然而然的，但它的理想化不应为该模型提供不切实际的力量模型。这样一个理想化的一个例子是图灵机的无限胶带。模拟计算机的问题带有实数，可以允许构建不合理的东西 Zeno机器. 。但是，已经在文献中提出并使用了几种此类模型（GPAC是此答案的主要主题，但我尝试在下面的列表中完成，而没有任何 超计算机):
- 这 通用模拟计算机 （GPAC），定义 克劳德·埃恩农（Claude E.Shannon） 在1941年（PAYWALLED PDF） 模拟 差分分析仪. 。 GPAC的定义最近进行了完善，其计算能力已被修订。
- 这 Blum-Shub-Smale机器, ，在离散时间上对实数。它与 真正的公羊 通常用于计算几何形状的模型；
- $ mathbb r $ - 记录功能;
- 神经网络;
- 可计算分析, ，查看图灵机可以计算的实数。
GPAC模型的功率
在 他的1941年报纸, ，Shanon引入了GPAC模型 差分分析仪。该模型只需要3种互连单元（常量单元，加法器和集成器。可以通过集成器和加法器构建乘数。）他表明，它生成的一组功能是代数差异功能集，但排除了该功能。 高转移功能. 。这意味着 $ gamma $ 和 $ zeta $, ，可以生成图灵竞争。换句话说，没有差分分析仪会拥有$ y（t）= gamma（t）$的输出，蚂蚁长期以来似乎是这样的模拟计算机不是“通用”的，因为它无法生成一些合理的可计算数学家使用的功能。
但是，在2004年， 丹尼尔·席尔瓦·格拉萨（Daniel SilvaGraça） 基于瞬时计算的先前模型过于限制。如果以不同的方式定义函数$ f $的可计算性，则允许$ y（t）$收敛到$ f（x）$，对于输入$ x $，则$ gamma $和$ zeta $函数为可以通过GPAC计算。 Bournez，Campagnolo，Graça和Hainry随后在2006年展出（付费 / 免费重印） 理想化的模型 其中允许在框架中计算所有可计算功能 可计算分析.
然后，Bournez，Graça和Pouly在2013年表明这些模拟计算机可以有效地模拟Turing Machine（大PDF的第181页），在2014年， 在该模型中，P和NP复杂性类是等效的。
建议可以通过无限神经网对通用模拟系统进行建模，即可以复制任何其他模拟系统输入/输出值以进行给定操作，并且可以根据需要链接操作？
虽然我确实自己提出了这个想法，但随后的搜索显示了类似的建议：
出现的是一个类似教堂的式论文，应用于模拟计算领域，该论述具有神经网络模型代替数字图灵机（请参阅 这里).
可以说，您所需要的只是原始操作将值从一个节点移至另一个节点。从袖口上可以加分，负和划分以获得连接之间的比率。
现在，关于棘手的问题，请查看神经网络成功应用的位置，或者由于在AA离散计算机上实施而正在执行。
（很抱歉，如果我对这个话题的几乎外行的看法非常明显）
