算法分析导论:图灵机、有效计算和计算模型
需积分: 5 88 浏览量
更新于2024-06-16
收藏 806KB PDF 举报
算法分析导论
在这篇讲义中,我们将探讨算法分析的基础知识,特别是图灵机的概念和历史背景。
**图灵机**
图灵机(Turing Machine,TM)是一种抽象的计算模型,由Alan Turing在1936年发明。图灵机可以计算任何通常被认为是可计算的函数;事实上,将可计算定义为图灵机可计算是相当合理的。图灵机的出现早于真正的计算机,dating back to the 1930s when mathematicians were trying to understand the concept of "effective computation".
**有效计算**
在20世纪30年代,数学家们尝试定义“有效计算”的概念以区分可计算和不可计算的问题。他们知道各种有效计算的算法,但他们不太确定如何以一种普遍的方式定义“有效计算”。为了确定这个概念,出现了几种不同的形式化方法,每种方法都有其自己的特点:
* 图灵机(艾伦·图灵)
* Post系统(埃米尔·波斯特)
* µ-递归函数(库尔特·哥德尔,雅克·埃尔布朗)
* λ-演算(阿隆佐·邱奇,斯蒂芬·克利尼)
* 组合逻辑(莫西斯·舒恩菲克尔,哈斯克尔·柯里)
所有这些系统都体现了一种或另一种形式的有效计算的思想。它们处理各种类型的数据;例如,图灵机操作有限字母表上的字符串,µ-递归函数操作自然数,λ-演算操作λ-项,组合逻辑操作由组合符号构建的项。
**数据表示**
所有这些不同类型的数据之间存在自然的转换。例如,让{0,1}∗表示字母表{0,1}上所有有限长度的字符串的集合。存在一个简单的一一对应关系{0,1}∗和自然数N={0,1,2,}之间,定义如下:
x → #(1x)−1,
其中#y是由二进制字符串y表示的自然数。相反地,将几乎任何东西(自然数、λ-项、{0,1,2,,9}∗中的字符串、树、图等)编码为{0,1}∗中的字符串是很容易的。在这些数据的自然编码下,所有上述形式主义都可以模拟彼此,因此尽管它们在表面上有所不同,但它们在计算上是等价的。
**现代计算机**
如今,我们可以毫不掩饰地利用我们更现代的视角,并将编程语言如Java或C(或它们的理想化版本)添加到这个列表中-与Church和G¨odel所必须努力应对的情况相比,这是一种真正的奢侈。在上面列出的经典系统中,最接近现代计算机的是图灵机。除了我们将在下面定义的现成模型外,还有许多定制变体(非-确定性、多带、多维带、双向无限带等),它们在计算上等效,即它们都可以相互模拟。
2024-02-03 上传
2024-02-03 上传
2024-02-01 上传
2024-01-12 上传
2023-06-21 上传
2023-09-09 上传
2023-05-17 上传
2023-05-26 上传
2023-09-06 上传
![](https://profile-avatar.csdnimg.cn/c2b45917171a45fa84394d093d82ce02_wizardforcel.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
绝不原创的飞龙
- 粉丝: 3w+
- 资源: 1088
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储