

首页  思维导图  详情



编程通识: 从图灵机到程序

2022-07-18 23:01:00   11  举报





AI智能生成

从计算机的诞生原理到程序的根本原理

图灵机

程序

编程

计算机

模版推荐

作者其他创作

大纲/内容

1.编程语言的模型:  数据与指令

所有编程语言的结构都类似, 都有数据与指令

数据的定义和处理

数据的操作

编程语言的起源

图灵机(最初是个硬件模型, 投射到计算机硬件; 抽象即是编程语言模型)

历史硬件: 纸带 + 读写头: 进行数据读取

表格: 限制读写顺序(规则)

读写头中的状态存储器: 根据读写数据映射状态进行操作

软件模型: 数据 + 指令

编程语言的设计依赖于计算机(硬件)的设计

通用计算机的主流实现方式

冯-诺依曼架构

单一内存空间

数据

程序

哈佛架构

内存空间1

数据

内存空间2

程序

历史上通用计算机的选型

是否有比图灵机更加完备的系统

通过哥德尔不完备定理得出不可能存在( 自我指涉的逻辑悖论 )

丘奇-图灵猜想

想要用形式化、通用的方法, 去解决尽可能多的问题, 图灵机的能力即是上限

任何可以用算法实现的计算, 都可以用图灵机实现. 图灵机就是算法解决问题的上线.

图灵完备

代表和图灵机有相同处理问题的能力

lambda演算

递归

面对对象

各大计算机原型

函数式编程的起源: lambda演算法

可以整明哥德尔不完备定理

迭代

元胞自动机

停机问题

停机问题（英语：halting problem）是逻辑数学中可计算性理论的一个问题。通俗地说，停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题：是否存在一个程序P，对于任意输入的程序w，能够判断w会在有限时间内结束或者死循环。 通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决，则有一个程序判断其本身是否会停机并做出相反的行为，这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。 停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。

2.编程与数学建模

对现实世界进行数学建模投射到程序世界中

现实中的数值

程序世界中的对象的属性

数值与数值的关系

程序中的函数

3.lambda演算法理解函数式编程

lambda演算法

最核心的概念: 函数 数据和指令是建立在函数之上的

是图灵完备的, 可以用函数虚拟出数据和指令

现代计算机中, 小数和四则运算都是基于自然数和加法的 即若lambda演算法能虚拟出自然数和加法, 即能虚拟出图灵机

python