Product Design, Manufacturing & Innovation Resources
家 » 图灵完备性

图灵完备性

1936
  • Alan Turing
计算机科学实验室展示编程语言的图灵完备性。.

(图片仅供参考)

一套数据处理规则系统,例如 编程语言, is Turing complete if it can simulate any single-taped Turing machine. This means it is computationally universal and can be used to solve any computable problem, given enough time and memory. Most general-purpose programming languages are Turing complete, forming the theoretical foundation for their expressive power.

Turing completeness is a concept from computability theory that defines the power of a computational system. It originates from Alan Turing’s 1936 paper describing a theoretical device known as the Turing machine. This machine consists of an infinitely long tape, a head that can read, write, and move along the tape, and a set of states and transition rules. Despite its simplicity, a Turing machine can perform any computation that can be described algorithmically. A 编程语言 or any other formal system is deemed ‘Turing complete’ if it has the capability to simulate a universal Turing machine. This implies that the language can compute anything that is computable.

系统要具备图灵完备性,核心要求是具备条件分支(如if-then-else语句)和无限循环或递归能力(如while循环、for循环)。这些构造使系统能够进行决策和重复操作,足以模拟图灵机状态转换与磁带操作的行为。 作为计算机科学基础原理的丘奇-图灵论题指出:任何被自然视为‘可计算’的函数,均可由图灵机实现。因此理论上,图灵完备语言能够表达任意算法。.

然而,这种理论威力也伴随着一个重大后果:停机问题。图灵证明,不可能创建一个通用算法,能够针对所有可能的输入确定任何给定程序是最终运行完成还是永远运行下去。这种不可判定性是所有图灵完备系统的固有属性。因此,一些领域特定语言被有意设计为非图灵完备的。例如,标准 SQL 和 HTML 就不是图灵完备的,这保证了它们的脚本或定义能够终止,并防止它们意外陷入无限循环,而这正是数据库查询和文档渲染所期望的特性。

UNESCO Nomenclature: 1202
- 计算机科学

类型

抽象系统

中断

递增

用法

广泛使用

前体

  • 库尔特 哥德尔§关于不完备性定理的工作
  • Alonzo Church’s development of λ演算
  • 大卫·希尔伯特将数学形式化的计划
  • 算法的概念可以追溯到古代

应用程序

  • 通用编程语言(python、c++、java)
  • 具有宏功能的电子表格系统(例如带有 VBA 的 Excel)
  • 我的世界中的红石电路
  • cellular automata 像康威的 人生游戏
  • 一些带有递归公用表表达式的高级 SQL 扩展
  • C++模板元编程子系统
  • css3 与某些 html 组合

专利:

NA

潜在创新理念

  • 一种可验证的、非图灵完备的智能合约语言,用于关键金融交易,防止无限循环和重入攻击。
  • 这是一款教育游戏,玩家可以通过基本逻辑门构建图灵完备机器来教授基础计算机科学。
  • 一种基于 DNA 的计算系统,利用图灵完备性在分子水平上进行复杂的生物模拟。
  • 一种量子编程范式,扩展了图灵完备性,以处理新算法的叠加和纠缠。
  • 一个 形式验证 tool that can prove or disprove the turing completeness of any given formal system or esoteric language.
  • 一种去中心化的网络协议,其中节点行为由小型、沙盒、图灵完备的脚本定义,以实现可定制的路由。
  • 一种艺术人工智能,通过探索简约、随机生成的图灵机的状态空间来生成新颖的视觉模式。
  • 一个安全分析框架,用于识别由配置文件中意外的图灵完备性导致的潜在拒绝服务漏洞。
  • a neuro-symbolic ai architecture where a 神经网络 learns to manipulate a turing-complete symbolic computation engine.
  • 基于fpgas的自修改硬件系统,其中硬件逻辑本身是一个可以进化的图灵完备系统。
相关主题:图灵完备性、图灵机、可计算性理论、艾伦·图灵、丘奇-图灵论题、通用计算、算法、形式语言、可判定性、停机问题。.

历史背景

图灵完备性

1925
1928
1930
1936
1940
1943
1950
1924
1925
1930
1931
1939
1940
1950
1950

(如果日期未知或不相关,例如“流体力学”,则提供其显著出现的近似估计)

第十年 周年纪念日

只有注册会员才能免费获取完整尺寸的图片和下载内容。

> 登录 <