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

图灵完备性

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

(图片仅供参考)

一套数据处理规则系统,例如 编程语言, 若能模拟任何单带图灵机,则该语言即为图灵完备。这意味着它具有计算普适性,只要有足够的时间和内存,就能解决任何可计算问题。大多数通用编程语言都是图灵完备的,这构成了其表达能力的理论基础。.

图灵完备性是可计算性理论中的一个概念,用于定义计算系统的能力。该概念源于艾伦·图灵1936年的论文,文中描述了一种名为图灵机的理论装置。该机器由无限长的磁带、可读写并沿磁带移动的读写头,以及一组状态和转换规则构成。尽管结构简单,图灵机却能执行任何可通过算法描述的计算。 若某种编程语言或其他形式系统具备模拟通用图灵机的能力,则被视为‘图灵完备’。这意味着该语言能够计算任何可计算的问题。.

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

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

UNESCO Nomenclature: 1202
- 计算机科学

类型

抽象系统

中断

递增

用法

广泛使用

前体

  • 库尔特·哥德尔关于不完备定理的研究
  • 阿隆佐·丘奇对lambda演算的发展
  • 大卫·希尔伯特将数学形式化的计划
  • 算法的概念可以追溯到古代

应用程序

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

专利:

NA

潜在创新理念

由于机器人流量被拦截(目前每天超过 4 万),此内容仅限社区成员查看。
> 登录 > 或者 > 注册 < (100% 免费)即可访问此内容,以及所有其他受限内容和工具。

相关主题:图灵完备性、图灵机、可计算性理论、艾伦·图灵、丘奇-图灵论题、通用计算、算法、形式语言、可判定性、停机问题。.

历史背景

图灵完备性

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

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

相关发明、创新和技术原理

只有注册会员才能免费获得 100% 的全尺寸图片和下载。.

> 登录 <