图灵完成的软件构造，语言和API的目录； 对于安全性和可靠性的意义。 应用程序：您的计算机中有多少台计算机？任何相当复杂的C或Fortran程序都包含新编写的，未指定的，有错误的且缓慢执行一半的Common Lisp语言的程序 。 -格林斯潘第十规则
图灵完整性 （TC）是系统的属性，可以用输入和输出的一些简单表示来实现任何可计算的功能。
图灵完整性是计算机科学中的基本概念。 它有助于回答许多关键问题，例如，为什么不可能创建完美的防病毒程序。 但是同时，这是一个非常
普遍的现象。 计算机系统似乎很难实现执行任何程序的通用性，但事实恰恰相反：很难编写出一个不会立即变成完整的图灵的有用系统。 事实证明，即使对输入数据进行一点控制并将其转换为结果，通常也可以创建一个图灵完整的系统。 它可能很有趣，有用（尽管
通常不是 ），有害或极其不安全，并且是黑客的真实礼物（请参阅
“语言理论安全性” ，该
语言研究“奇怪机器”的黑客方法
1） ） 这种行为的惊人例子提醒我们，图灵完整性潜伏在各处，保护系统极为困难。
过于强大的编程语言也会引发令人不快的DoS攻击。
Fazzer afl在
OpenBSD中发现了这种
roff ，它能够生成
无限循环 ，从而滥用了一些字符串替换规则。
这些图灵完备系统的意外示例可能更好地被视为“发现的”或“发现的”
深奥编程语言的子集。 因此，极简的
FRACTRAN不被视为
2 ，以及经过特别迷惑的语言
Malbolge （编写微不足道的程序将花费数年），因为这些语言是经过特殊设计的深奥的YaP。 此外，“
生活”游戏不包含在我们的子集中，因为有关图灵完整性的问题在其发布后立即出现，并且对其完整图灵的认可并不令人惊讶。 鉴于路由和数据包交换网络的复杂性，可以在这些网络上
构建蜂窝自动机或对
逻辑方案进行编程也就不足为奇
了 ，票务计划/验证不仅是
NP困难甚至EXPSPACE困难的任务，而且也是完全无法解决的 （由于复杂的航空公司规则）。
事实证明，许多配置，特殊语言，工具或复杂的游戏违反了
最低限度的
规则，并
“意外地变成了图灵完整” ，例如
MediaWiki ，
sed 模板或编辑器中
重复的regexp / find-replace命令 。 一般而言，任何形式的
行替换或模板化或即时生成的可能性都很高，它们本身就是图灵完备的系统，或者是重复的，因为它们通常支持
lambda演算或语言或标签
术语的重写 ，例如深奥的语言“
/// ”或
星期四 。
XSLT ，
无限扫雷 ，
矮人 要塞 3 ，Starcraft，
Minecraft ，
Ant ，
Transport Tycoon ，
C ++模板和
Java概论 ，
DNA计算等-所有这些都是图灵完备的系统，这也不足为奇。 许多游戏都支持脚本以简化开发和自定义mod。 因此，要使图灵完备的游戏成为基本游戏，只需打开语法即可调用更知名的语言，例如Perl。
图灵完整性可能只是标准格式中鲜为人知的部分。 可能在我们这个时代，许多人都不知道TrueType和许多字体是堆叠计算机上的PostScript程序，类似于
ELF元数据和DWARF调试信息 。 或者
某些音乐格式超出了
MIDI ，还支持脚本并需要解释。 如果您知道字体的图灵完整性，那么TeX文档的图灵完整性就不足为奇了，这自然会在字体和媒体中引起许多严重且有趣的安全漏洞，例如
BLEND或Linux
SNES和
NES利用。 在其他格式（如PDF）中，漏洞数量非常之多
4 。 同样，出色的成就，例如用乐高积木或
多米诺骨牌制造小型图灵机
5 由于我们早就知道机械计算机的工作原理，因此没有考虑。
另一方面，称为“怪异机器”的一系列计算机安全研究通常揭示出真正令人惊叹的图灵完整系统。 而且，它们在不同程度上给不同的人带来惊喜：一个人看起来很不寻常，不会让其他人感到惊讶。
以下系统可能会意外完善：
- 没有点击的CSS
- SVG：PostScript在设计上是TC，但是更现代的SVG矢量图形格式是用XML编写的，也就是使用（通常）图灵不完整的文档语言呢？ 与XSLT结合使用似乎仍然如此，但是在Web浏览器的通常情况下，我还没有发现任何证据或证明。 SVG标准很棒，有时甚至令人恐惧：SVG 1.2标准的不成功版本试图增加在SVG映像中打开网络套接字的功能 。
- Unicode ： Nicholas Seriot建议双向Unicode算法 （旨在显示从右到左的脚本，例如阿拉伯语或希伯来语）可能足够复杂，以通过区分大小写的规则（例如土耳其语）支持标签系统。
另请参阅
参考文献
应用程式
您的计算机中有几台计算机？
有些人陷入了关于奇怪的汽车或AI代理将变得有多“大”的争执中：将创建一个这样的，两个，十个或数百万个代理。 没关系，因为这只是组织方面的事情。 实际上，系统的输入和输出很重要：整个系统的效率如何？它消耗哪些资源？ 没有人会在乎Google是在50台超级计算机，50,000台大型机，500万台服务器，5000万台嵌入式/移动处理器或
以上所有功能的组合上运行 。 谷歌使用各种芯片都没关系：从自制的“张量处理器”到独特的硅处理器（英特尔将其用于Xeon处理器的芯片出售给许多主要客户），FPGA，GPU，CPU，甚至是更奇特的设备，例如
D-Wave量子计算机。 保持竞争力并以适度的费用提供服务仅是重要的。 最后，如今，一台超级计算机通常看起来像是带有大量GPU和非同寻常的高速InfiniBand连接的大量机架服务器。 也就是说，您可能会认为超级计算机与数据中心没有太大区别。 列出的任何设备都可以支持众多奇怪的机器，具体取决于其内部动态和连接性。
类似地，任何AI系统都可以以异步运行的一个巨型神经网络或许多单独的神经网络的形式实现，或者作为一组异构的微服务实现，或者作为“思想社会”来实现。 所有这些都不是特别重要。 从复杂性或风险的角度来看，在系统工作时如何组织它并不重要。 可以在许多层次上看到该系统，每个层次本身都是同等无效的，但是对于通用系统中的不同目的很有用。
这是一个定义不明确的问题的示例：您的口袋和书桌上现在有几台计算机？ 您的“计算机”中有多少台计算机？ 只想一个吗？ 让我们仔细看看。
不仅仅是CPU：如今，晶体管和处理器内核是如此的便宜，以至于现在常常有必要为实时任务分配单独的内核，以提高性能，安全性，避免加载主操作系统，与旧体系结构或硬件兼容。现有软件包。 仅仅是因为DSP或内核的编程速度比创建专用ASIC的编程速度快，或者是因为它是最简单的解决方案。 另外，许多这些组件可以用作计算元素，即使它们不是故意的，甚至隐藏了此功能。
因此：
- 在传统的英特尔处理器中，数十亿个晶体管执行许多任务：
- 2-8个主处理器内核中的每个内核都可以独立工作，并根据需要打开和关闭，它具有自己的缓存（直到最近，大多数计算机中的RAM都比RAM大），因此应将其视为独立的计算机。
- 例如，通过微代码对CPU进行整体重新编程，以消除芯片设计错误，并炫耀越来越不透明的对象，例如Intel Management Engine（使用JVM进行编程 ； Rouen，2014和SGX ）或AMD的Platform Security Processor （PSP），或者Android TEE 通常，这些硬件模块本身就是成熟的计算机，独立于主机运行，并且可能会干扰其运行。
- 按照FRACTRAN的精神，通过在浮点运算中进行编码，任何FPU都可以成为图灵完备的系统。
- 如上所述，可以将MMU编程到奇怪的页面错误计算机中。
- DSP模块，定制芯片。 可能，用于h.264之类的视频格式的ASIC不会成为图灵完整的系统（尽管支持复杂的增量和压缩方法， 可能允许使用Van Tile之类的东西）。 但是， Apple A9移动SoC远远超出了带有集成GPU的常规双核ARM处理器。 像Intel或AMD台式机芯片一样，它包含一个称为Secure Enclave（物理专用处理器内核）的安全环境，但它还包含一个用于图像的协处理器，一个用于语音识别的协处理器（部分支持Siri）以及其他几个内核。 这些ASIC有时用于AI任务，并且显然专门用于神经网络的矩阵乘法，并且由于递归神经网络已经完成了图灵完善，所以...您了解。 摩托罗拉，高通和其他公司也急于扩展其SoC。
- 主板BIOS和/或网络访问控制芯片。
- 马克·埃莫洛夫 （ Mark Ermolov）指出：
“令人惊讶的是，英特尔Silvermont Moorefield SoC（ANN）中集成了多少个异构处理器内核：x86，ARC，LMT，8051，音频DSP，每个都有其自己的固件并支持JTAG接口
这些控制或调试芯片可以“意外”在售后的设备上保持激活状态，例如Via C3 CPU中的内置ARM。 - GPU具有数百或数千个简单的内核，每个内核都可以很好地与神经网络配合使用或执行通用计算（尽管比处理器慢）。
- 磁带，硬盘驱动器，闪存驱动器和SSD控制器通常在ARM处理器上运行，以运行内置实用程序来执行诸如从操作系统隐藏坏扇区之类的任务。 他们可以被黑客入侵。 但是ARM处理器用于大多数嵌入式应用程序，因此ARM喜欢吹嘘“现代智能手机包含8到14个ARM处理器，其中一个是应用程序处理器（运行Android或iOS），另一个是用于频段堆栈的处理器。 （基带堆栈） 。 ”
- 网络芯片对DMA执行独立的处理（这要归功于诸如网络唤醒 工作之 类的局域网唤醒之类的独立功能）。
- 智能手机：除了上述所有功能之外，还有一个独立的基带处理器 ，该处理器在其自己的实时操作系统下运行，以处理与手机信号塔/ GPS / GPS等的通信。 如果您使用L4之类的虚拟化，甚至更多。 除了其他漏洞之外，基带处理器中还已经检测到后门。
- 用于智能手机的SIM卡不仅仅是存储用户数据记录的存储卡。 这些是可以独立运行Java Card应用程序的智能卡 （也可能是NFC芯片）。 就像IME中的JVM。 当然，SIM卡可以被黑客入侵并用于监视等。
- 通过USB或主板连接的设备可以配备自己的处理器。 例如，WiFi适配器，键盘，鼠标等。从理论上讲，它们中的大多数与通过DMA和IOMMU对主机的直接干扰是隔离的，但细节在于...
- 随机的怪异芯片，例如运行WatchOS的MacBook Touch。
- ...
因此，从图灵完备的设备的意义上说，在普通的智能手机或台式计算机中，将会有15到数千台计算机。 它们每个都可以进行编程，它具有足够的能力来运行许多程序，并且攻击者可以使用它们来监视，窃取或攻击系统的其余部分。
在历史环境中没有什么不寻常的，因为即使最开始的大型机通常也包括几台计算机，在这些计算机中，主计算机执行批处理，而辅助计算机提供高速I / O操作，否则将干扰其中断。
实际上，除了信息安全社区（由于所有这些计算机都是不安全的，因此对NSA和病毒编写者有用）之外，所有其他用户都不在乎我们计算机的内部是疯狂复杂的系统，更准确地说，这是数百个杂乱无章的杂物。计算机彼此尴尬地连接在一起（不清楚，“网络就是计算机”还是“计算机就是网络”……？）。用户将其感知并用作一台计算机。
1.研究的一个活跃领域是创建经过精心设计并保证不会完全完善的语言和系统（例如，完全功能性的编程）。为什么要花太多精力来创建一种许多程序都无法编写的语言？事实是，图灵完备性与哥德尔的不完备性定理和赖斯定理密切相关。。因此，如果允许使用TC，那么我们将失去所有可能的可证明性。相反，各种有用的东西很容易用图灵不完整的语言证明：例如，一个程序是完整的，是否类型安全的;很容易转换为逻辑定理;它消耗的资源有限;协议实现是真实的或等效于另一种实现。很容易证明没有副作用，并且可以将程序转换为逻辑上等效但速度更快的选项（这对于声明性语言（例如SQL）尤其重要，在SQL中，优化器转换查询的能力是获得可接受性能的关键。尽管当然，使用SQL可以完成惊人的事情，如面向机器学习模型的梯度下降，以及一些SQL扩展，使其无论如何都可以完整完成，允许您编码循环系统，modelDSL或调用PL / SQL等。以下是一些有关怪异汽车的文献：↑2.尽管线性神经网络利用四舍五入到零的浮点模式来编码潜在的图灵完备行为（对于RNN），但在正常操作中是不可见的，这也是随机的图灵完备行为并且是安全语言的一个很好的例子。 ↑3. 矮人要塞提供发条，因此图灵的完整性不足为奇。但是水也被实现为一个简单的细胞自动机，因此，还有更多的方法可以确保图元的完整性！现在，游戏Wiki列出了四种创建逻辑门的潜在方法：液体，时钟机制，矿车以及带有门和压力传感器的生物/动物逻辑门。 ↑4.完整的PDF规范异常膨胀。例如，在像Google Chrome浏览器这样的支持大量PDF规范的简单PDF查看器中，您可以播放Breakout（因为PDF包含其自己的怪异JavaScript子集）。官方的Adobe PDF查看器最多支持3D CAD功能。 ↑5.请参阅Think Math上的多米诺逻辑门和4位多米诺关节加法器的演示。 ↑