编程通识: 从图灵机到程序
2022-07-18 23:01:00 11 举报
AI智能生成
从计算机的诞生原理到程序的根本原理
作者其他创作
大纲/内容
1.编程语言的模型: 数据与指令
所有编程语言的结构都类似, 都有数据与指令
数据的定义和处理
数据的操作
编程语言的起源
图灵机(最初是个硬件模型, 投射到计算机硬件; 抽象即是编程语言模型)
历史硬件: 纸带 + 读写头: 进行数据读取
表格: 限制读写顺序(规则)
读写头中的状态存储器: 根据读写数据映射状态进行操作
软件模型: 数据 + 指令
编程语言的设计依赖于计算机(硬件)的设计
通用计算机的主流实现方式
冯-诺依曼 架构
单一内存空间
数据
程序
哈佛架构
内存空间1
数据
内存空间2
程序
历史上通用计算机的选型
是否有比图灵机更加完备的系统
通过哥德尔不完备定理得出不可能存在( 自我指涉的逻辑悖论 )
丘奇-图灵猜想
想要用形式化、通用的方法, 去解决尽可能多的问题, 图灵机的能力即是上限
任何可以用算法实现的计算, 都可以用图灵机实现. 图灵机就是算法解决问题的上线.
图灵完备
代表和图灵机有相同处理问题的能力
lambda演算
递归
面对对象
各大计算机原型
函数式编程的起源: lambda演算法
可以整明哥德尔不完备定理
迭代
元胞自动机
停机问题
停机问题(英语:halting problem)是逻辑数学中可计算性理论的一个问题。通俗地说,停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。
通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。
通俗的说,停机问题就是判断任意一个程序是否会在有限的时间之内结束运行的问题。如果这个问题可以在有限的时间之内解决,则有一个程序判断其本身是否会停机并做出相反的行为,这时候显然不管停机问题的结果是什么都不会符合要求。所以这是一个不可解的问题。
停机问题本质是一高阶逻辑的不自恰性和不完备性。类似的命题有理发师悖论、全能悖论等。
2.编程与数学建模
对现实世界进行数学建模投射到程序世界中
现实中的数值
程序世界中的对象的属性
数值与数值的关系
程序中的函数
3.lambda演算法理解函数式编程
lambda演算法
最核心的概念: 函数
数据和指令是建立在函数之上的
数据和指令是建立在函数之上的
是图灵完备的, 可以用函数虚拟出数据和指令
现代计算机中, 小数和四则运算都是基于自然数和加法的
即若lambda演算法能虚拟出自然数和加法, 即能虚拟出图灵机
即若lambda演算法能虚拟出自然数和加法, 即能虚拟出图灵机
python
即是图灵机与lambda演算法的融合
4.深度学习与元胞自动机
元胞自动机
最早由冯诺依曼提出
通过<生命的游戏> 整明元胞自动机能够虚拟出一个电子计算机(从逻辑门开始),
即是图灵完备的
即是图灵完备的
元胞自动机不适合通用编程, 尽管其图灵完备
因为其没有数据和指令的概念, 只能从元胞群体得到目标结果, 对个体不能很好地控制
因为其没有数据和指令的概念, 只能从元胞群体得到目标结果, 对个体不能很好地控制
优势
<吃豆人>的遗传算法, 和现实生活中的自然演化/优胜略汰的无法规约的现象,
图灵机和lambda的范式天然和演化不兼容, 这些情况元胞自动机更适合
图灵机和lambda的范式天然和演化不兼容, 这些情况元胞自动机更适合
5.软件工程如何影响编程
<人月神话>
大型项目开发中, 投入人数居多, 不仅不会加快开发速度, 反而会产生更多问题花费时间.
服务调用之间的人员沟通效率随着服务方的参与人数指数增加
服务调用之间的人员沟通效率随着服务方的参与人数指数增加
功能之间的解耦
时间上动静态部分代码的解耦
领域驱动模型DDD
基于MVC三层架构,
从核心业务中挑选最稳定的组成中台
即以业务领域作为核心驱动设计
从核心业务中挑选最稳定的组成中台
即以业务领域作为核心驱动设计
敏捷开发
小步快跑, 及时反馈, 快速试错
优势: 组织架构减少分层避免信息失真, 让需求提出者、设计者、开发者耦合以提高效率
操作系统内核与开源
为了追求某些功能的极致效率, 代码复杂性换来了性能. 放弃了部分模块化和分层化的可能. 函数耦合严重.
为了完善与实现这么个复杂的系统, 可以选择开源.
为了完善与实现这么个复杂的系统, 可以选择开源.
0 条评论
下一页