7,129
个编辑
更改
跳到导航
跳到搜索
第55行：
第55行： + + + + + + + + + + + + + + + + + + + +
→编者推荐
Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。<ref name=":3">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=[[Proceedings of the Royal Society A]]|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546|bibcode = 2005RSPSA.461.3473A |arxiv=quant-ph/0412187}} Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</ref>
Scott Aaronson 定义了具有后选择功能的量子图灵机，他证明了这种机器上的时间复杂度类 (PostBQP) 等于经典复杂度 PP。<ref name=":3">{{cite journal|last=Aaronson|first=Scott|year=2005|title=Quantum computing, postselection, and probabilistic polynomial-time|journal=[[Proceedings of the Royal Society A]]|volume=461|issue=2063|pages=3473–3482|doi=10.1098/rspa.2005.1546|bibcode = 2005RSPSA.461.3473A |arxiv=quant-ph/0412187}} Preprint available at [https://arxiv.org/abs/quant-ph/0412187]</ref>
==参考文献==
<references/>
==编者推荐==
==编者推荐==
===集智文章推荐===
*[https://swarma.org/?p=3652 神经网络与图灵机的复杂度博弈]
::1931年，天才数学家图灵提出了著名的图灵机模型，它奠定了人工智能的数学基础。1943年，麦克洛克 & 皮茨（McCulloch & Pitts）两人提出了著名的人工神经元模型，该模型一直沿用至今，它奠定了所有深度学习模型的基础。那么，这两个开山之作究竟是怎样一种相爱相杀的关系呢？天才数学家冯诺依曼指出，图灵机和神经元本质上虽然彼此等价，我们可以用图灵机模拟神经元，也可以用神经元模拟图灵机，但是它们却位于复杂度王国中的不同领地。神经网络代表了一大类擅长并行计算的复杂系统，它们自身的结构就构成了对自己最简洁的编码；而图灵机则代表了另一类以穿行方式计算的复杂系统，这些系统以通用图灵机作为复杂度的分水岭：一边，系统的行为可以被更短的代码描述；另一边，我们却无法绕过复杂度的沟壑。而先进的深度学习研究正在试图将这两类系统合成为一个：神经图灵机。
===课程推荐===
*[https://campus.swarma.org/course/1155 图灵机]
::本课程将围绕图灵机，详细介绍图灵机的定义、图灵机的计算、图灵机框架的模拟、通用图灵机、以及图灵停机问题，说明算法的上界。
*[https://campus.swarma.org/course/1153 人工智能2020]
::本课程为北京师范大学系统科学学院张江教授开设的研究生课程《人工智能》课程回放。课程偏重理论，辅以编程实践，将粗粒度的梳理人工智能重要的理念、算法、模型。前面会包含一些人工智能之前的理论计算机模型，图灵机等，后面系统从两方面讲解，一是符号派的人工智能，包括搜索、推理、表示等；二是连接派的人工智能，机器学习，强调理论机器学习基础。
===文章推荐===
*[https://pattern.swarma.org/paper?id=9207a15c-9b1d-11ea-abd6-0242ac1a0005 分子计算：通向化学图灵机的途径。]
::为了顺应快速增长的信息存储和处理需求，需要新的计算策略。分子计算的想法（即通过分子、超分子或生物分子方法进行基本计算，而不是通过电子方法）长期以来一直吸引着研究人员。使用分子和(生物)大分子进行计算的前景并非没有先例。自然中充满了以高效率、低能量成本和高密度信息编码来处理和存储数据的示例。根据通用计算方法运行的计算机的设计和组装，例如图灵机中的计算机，未来可能会以化学的方式实现。从这个角度来看，本文章重点介绍了到目前为止已经设计和合成的分子和(生物)大分子系统，目的是将它们用于计算目的；还提出了分子图灵机的蓝图，它基于一个催化装置，它沿着聚合物带滑动，在移动时，以氧原子的形式在这条带上打印二进制信息。
[[文件:展示现代计算技术和未来分子计算的发现和进展的时间表.jpg|缩略图|右]]
*[https://pattern.swarma.org/paper?id=14ecc15e-8860-11ea-b132-0242ac1a000b 使用图灵机的图灵模式：出现和低层次结构形成。]
::尽管阿兰·图灵(Alan Turing)在1952年发表的关于形态发生的论文中提出了常微分方程的反应扩散模型，反映了他对数学生物学的兴趣，但他从未被认为接近过细胞自动机的定义。然而，他对形态发生的处理，特别是他发现的与对称破缺导致的某些形式的不均匀分布有关的困难，是将他的普遍计算理论与他的生物模式形成理论联系起来的关键。建立这样的联系并不能克服图灵所担心的特殊困难，无论如何，这个问题已经在生物学上得到了解决。但相反，这里开发的方法抓住了图灵最初关心的问题，并通过算法概率的概念为更一般的问题提供了一个低级解决方案，从而将图灵模式形成和通用计算这两个他对科学最重要的贡献联系在了一起。本文将展示使用此方法的一维模式的实验结果，而不会损失对n维模式泛化的一般性。