跳至主要內容

编程通识

LincZero大约 7 分钟

编程通识

目录

编程通识

参考：https://www.bilibili.com/video/BV123411p7rf

通用计算机

各种计算机语言通用的东西：

  • 通用性：专用计算机、通用计算机（图灵完备）
  • 通用计算机模型（实现方法）：图灵机、Lambda演算法系统、元胞计算机、递归、面向对象 等等
    • 相同点和区别
      • 相同点：解决问题的能力等价，都是图灵完备的 并且这几个模型都是可以互相虚拟的
      • 不同点：对问题的拆解、建模，把问题投射到数据模型上，有区别
    • 图灵完备
      • 图灵机、Lambda演算法系统、元胞计算机都是图灵完备的
      • 邱奇-图灵猜想：“任何可以用算法实现的计算，都可以用图灵机实现”，没有更完备的了
      • 也叫图灵完备：代表和图灵机有相同处理能力。图灵机、Lambda演算法系统、元胞计算机都是图灵完备
    • 超越图灵机？
      • 比图灵机更完备的：可能量子计算机、大脑、宇宙能吧，反正搞不来。例如宇宙还有 "真·随机"、自我指涉
    • 图灵完备的局限性
      • 不是所有东西都能解决。比如不能解决停机问题："设计一个程序来判断，另一个图灵机程序是否可以在有限时间内完成"
      • 哥德尔不完备定理：理想系统不存在。自我指涉的逻辑悖论
  • 计算机的内存结构：冯诺依曼结构、哈佛结构

图灵机

计算机语言的特性（拆分方法）

程序 = 数据 + 指令

现在基本都是用的图灵机，计算机语言也基本都满足这个特性

优点

（为什么现在都用的图灵机而不用图灵完备的其他模型呢）

  • 是最直观、最容易工程实现的方案
  • 图灵机可以让问题的拆解和解构更容易 图灵机的基础模块就是 “数据+指令“（将实际问题拆成数据和指令就很容易建模了、方便程序设计） 数据类型：类似于物理中的量纲

Lambda演算法（λ演算法）

图灵的老师 —— 邱奇提出来的

Lambda演算法

又分无类型lambda演算和有类型的。例如LISP只有两种数据结构，原子（atom）和表（list）

计算机语言的特性（拆分方法）

核心概念：函数 图灵机中的 数据或指令 在这里都可以用函数来表示 Lambda演算法中的符号不重要，重要的是符号和符号之间的关系 一个lambda表达式通过另一个lambda表达式可以变成一个新的lambda表达式，能把一种关系变成另一种关系

表示方法如图

image-20220516065258452
image-20220516065258452

相关语言

（这种函数式编程语言基于Lambda演算法，不过现在用的都是在图灵机上进行了lmabda演算的虚拟）

  • Haskell

  • LISP （就是那个偷火箭LISP代码的笑话）

    LISP是一种通用高级计算机程序语言，长期以来垄断人工智能领域的应用。 LISP作为应用人工智能而设计的语言，是第一个声明式系内函数式程序设计语言（最早的函数式编程语言）， 有别于命令式系内过程式的C、Fortran和面向对象的Java、C#等结构化程序设计语言

    LISP名称源自列表处理（LISt Processing）的英语缩写，由来自麻省理工学院的人工智能研究先驱约翰·麦卡锡（John McCarthy）在1958年基于λ演算所创造，采用抽象数据列表与递归作符号演算来衍生人工智能

    (DEFUN HELLO ()
  "HELLO WORLD"
)

使用lambda演算法虚拟出图灵机

  • 虚拟 图灵机中的 “数据”

    image-20220516065924737
    image-20220516065924737

  • 虚拟 自然数

    image-20220516070721003
    image-20220516070721003

  • 后继函数（可以理解成 x+=1 的意思）

    image-20220516071101842
    image-20220516071101842

  • 加法函数

    image-20220516071219028
    image-20220516071219028

与函数式编程

  • 函数式编程来源于Lambda演算法

    • 柯里化、闭包、匿名函数等，都来源与lambda演算法

    • lambda演算法中的函数都是匿名函数

      （js中的匿名函数又能写成箭头函数）

区别与优点（对比图灵机）

  • 定义上的区别
    • 图灵机：操作可以自由定义，往往特事特办，当面对特殊情况、无法预料的情况时处理不了
    • Lambda演算法：操作不是被定义出来的，而是定义数据后找规律，把操作给找出来 函数式编程会有更少的bug。这也是强类型所导致的，lambda的数据类型非常强
    • 图灵机要求你清楚所有情况再定义，lambda是定义规律
  • 相关程序设计语言
    • 图灵机：声明式系内函数式程序设计语言（函数式编程语言）
    • Lambda演算法：命令式系内过程式程序设计语言
  • 应用
    • 图灵机：擅长解决工程问题 更像是工程师
    • Lambda演算法：LISP：最开始就与AI开发有关、与自然语言处理 (非AI 纯靠逻辑的那种) 有关 更像是数学家物理学家

元胞自动机

最早由冯诺依曼提出，但没重视，跑去弄冯诺依曼结构了

计算机语言的特性（拆分方法）

核心：元胞

不能拆成指令和数据，和图灵机或Lambda演算法的范式有着本质不同

相关“语言”

没有针对它的计算机编程语言，没有编程方案，

但是有元胞计算机相关的东西：《生命的游戏》

《生命的游戏》

四条规则：

一个元胞周围的元胞数为 0：死亡 一个元胞周围的细胞数为 2/3：适应 一个元胞周围的细胞 >4：拥挤、消失 一个空格周围有3个元胞：重生

产生情况：

不变 周期 移动（飞船，移动速度最快为2回合一格，有点光速的感觉） 复制（高斯帕机枪）

还可以用生命游戏模拟生命游戏

图灵完备性

《生命的游戏》中，

飞船相撞：相当于非运算

区别和优点

吃豆游戏中的遗传算法

约翰霍兰德，用计算机做的一个实验

当时霍兰德研究的是进化策略，他的这篇开山之作叫《自然与人工系统中的适应》，研究的内容，可以简单的描述为吃豆游戏 [吃豆游戏中的遗传算法](https://sq.sf.163.com/blog/article/197481681108668416)

这种的最优方法没有规律，图灵机和Lambda演算法不好弄，Lambda演算法没法发现规律，用元胞计算机这种群体的自动演算会好一点

冯诺依曼瓶颈

图灵机有冯诺依曼瓶颈：内存读写性能拖累cpu，cpu毕竟只能线性读写

元胞计算机没有，没有cpu。模型运算是群体涌现出来的

有点像脑神经元，但应该也没超越图灵完备

文小刚，凝聚态理论里的大佬，理论物理最高奖狄拉克奖的获奖者

深度学习、神经网络、元胞自动机、类脑芯片

可以在计算机中虚拟神经网络，但硬件结构还是有限制，于是类脑芯片的概念被提出来了

类脑芯片，由许多的存算一体单元组成。或者用门电路和电容实现、 或者用忆组器 (特殊电阻，可以对之前留过它的电流形成记忆，类似于使用较多的神经元会变粗) 实现

区别

  • 传统芯片
    • 基本范式：门电路
    • 使用方式：编程，数据+指令
  • 忆阻芯片
    • 基本范式：电流和电阻之间的关系
    • 使用方式：学习、自适应。没法有目的地修改