← 花园

2023 主题

冯诺依曼《计算机与人脑》笔记

2023-03-01 · 持续修订


冯诺依曼《计算机与人脑》笔记

整理自印象笔记导出(2023)。原始导出:2023印象笔记导出

→ 附件 PDF → 附件 PDF

导读

冯诺依曼在计算机领域的成果

冯纽曼认为强大的计算机会给数学家们提供“促进整个数学界发展的启发”,这一想法来源于他的强烈信念,即抽象科学来自现实问题,即使纯数学中间的问题和思辨也是源于实证科学的。“„„当代数学最好的启发和动力„„就是来源于自然科学。”他认识到,数学并不是一种实证科学,而数学家们对数学问题进行选择以及决定成功的标准,往往是一种科学上的审美。

“我大致这样认为(由于问题太复杂了,所以我只能说大概是这样):数学的所有思想都来 源于经验,虽然这些思想的形成历程很长、很模糊。但是,数学思想一旦创生了出来,它就具有了自己的生命,而且就像真正的生命一样具有创造力。这种形式的生命主要由纯粹的审 美动机支配,而几乎同经验世界脱离了关系。然而,在这里,我想特别强调的一点是……如 果一个数学主题已经远离了所有的实证源头,而且仅仅跟一些非常‚抽象‛的领域有交叉的时候,这个数学主题就会濒临衰退了……无论这一阶段何时来到,唯一补救的办法就是在它 的源头处重生:重新注入或多或少的实证经验。”

这就是说,实证科学在纯数学中同样起到了一种启发性的作用:实证科学为数学提供了问题、 还提示了为这些问题寻找解答的概念与原理。虽然冯纽曼从没这样说过,但是我想他会认为 计算机的启发式应用可以在数学的一些领域扮演类似的角色。在第一个讲座中,他曾说纯数 学中的那些最强有力的方法来自数学家对于问题的直觉经验和实践理解,这一点与人们在利 用计算机对非线性偏微分方程求解的情况极其相似。

编程与流程图

为了在日常语言的数学计算描述和对应机器语言的程序之间架起桥梁,冯纽曼发明了流程 图。一个流程图是一个带着各种符号标记的图,它由很多图框以及连线组成。图框有几种类 型:操作框(规定了计算的非递归部分),选择框(对应于控制指令的有条件的跳转,并用 跳转条件来标注),替换与声明框(表示了递归的索引值),存储框(给出了内存关键部分在 某一个计算阶段的内容),并且用圆圈来标注程序的开始和结束以及相互联系。在执行与流 程图相应的程序的时候,计算机相当于是在流程图上行走,从开始圆圈出发,按照操作框中 的指令序列进行执行,根据选择框中的跳转标准进行循环或者到流程图其它部分的分支。有 向直线代表了图上流动的方向,最后在图上的某点汇合,无向的直线用来连接存储框与图上 的对应于存储内容作为计算对象的某个点。

当程序员解决一个复杂问题的时候,很有必要事先编好整个流程图。任何一个比较复杂的问 题都会由很多子问题构成,我们可以事先为这些子问题编好流程图和子程序。事先要准备一 些子程序来处理求解问题过程中所用到的大量的基本算法:例如十进制到二进制的相互转 换,双精度运算,各种积分和插值方法,网格和排序算法,等等。这些子程序可以存放在一 个磁带库中以备调用。为了解决一个具体问题,程序员只需要写下一个“母程序”,告诉计 算机如何从纸带上调用正确的程序,并且为了特定的问题如何修改这些子程序。

使用子程序的组合以及子程序库是让计算机协助编写程序的第一步。在这样的系统中,所有 的东西都需要由程序员用笨拙的“机器语言”书写。更好的办法是构建一套“程序员的编程 语言”,程序员可以用这种编程语言来写程序,然后使用机器语言编写一个编译程序,使得 机器可以自动把编程语言写的程序翻译成用机器语言所写的相应程序。这种编程语言将更接 近数学家、科学家以及工程师所熟悉的日常的或者数学的语言,而且也更容易被使用。这种 方法现在称为自动编译。冯纽曼使用“短代码”(编程语言)和“完全代码”(机器语言)来 表示它们19。

冯纽曼认识到,自动编译的概念可以看成由图灵证明的通用图灵机的一个实例。图灵机是一 个有限自动机加上无限长度的记录纸带。任意通用目的的计算机,加上一个能够无限修改纸 带存储的读写装置,都可以看作是图灵机。而通用图灵机 U 拥有以下属性:对于任意的图 灵机 M,都存在一个有限的程序 P 使得机器 U 在 P 的指导下可以计算与 M 相同的结果。也 就是 U 和 P 可以模拟 M。

自动编译当然也涉及到了模拟。设 Ue 为一个使用机器语言,程序员不方便使用的机器。程 序员使用编程语言会更方便。从理论上可以证明,我们可以构建一台机器来直接理解编程语言;我们把这个假想的计算机叫做 Mp。Pt 可以把编程语言翻译成 Ue 的机器语言的程序(用 机器 Ue 的语言写成)。那么 Ue 将会在 Pt 的指挥下计算出与 Mp 完全一样的结果。也就是说 Ue 加上 Pt 模拟了 Mp,这就是图灵机 U 与 P 能够模拟 M 的特殊情况。

注意,在 Ue 中有两种语言:一种是计算机直接使用的机器语言,另一种是通过编译程序 Pt 间接使用的程序员语言。冯纽曼把这些称为机器的“初级”和“高级”语言。初级语言主要 用于机器中的通讯与控制,而高级语言是我们人类与机器通信的语言。冯纽曼由此假设,也 许在人类的神经系统中也存在这样的初级与高级语言,而且这两种语言非常的不同。

“因此,神经系统也可能使用着与我们所熟悉的一般算术和数学非常不同的概念体系……无论中枢神经系统使用什么语言,有可能它们的逻辑与代数的深度都比我们通常使用的 要浅。 因此,当我们把中枢神经系统中的逻辑与数学看作一种语言的时候,它们必然会与我们通常 经验的语言在结构上本质的不同。 ……当我们讨论到数学的时候,我们可能谈论的是一种高级语言,但是它是在初级语言这种 中枢神经网络主要使用的语言之上构建的。”

他认为神经系统的初级语言从本质上具有统计特征。因此,他关于概率逻辑的工作就是与这 种语言有关的。参见本文集的第一部分的第三和第四个讲座以及“概率逻辑以及用不可靠元 件合成可靠有机体”,其中有他关于概率逻辑以及可靠性的讨论。

信息自动化转换机制

  1. 机器语言的转换机制:

背景:编程语言的编译器或解释器在计算机科学中充当信息转换机制,将高级语言转换为机器可以执行的低级语言。

操作:这种转换机制将复杂的任务简化,允许我们以更简单的方式处理任务,而不需要关心底层的实现细节。

结果:这种机制使我们能够更好地利用有限的资源,更有效地完成任务。

2.  Brainish语言的转换机制:

背景:Brainish被描述为一种多模态内部语言,由CTM(Conscious Turing Machine,意识图灵机)的处理器用来相互通信。

操作:Brainish实现多模态融合、多模态翻译和多模态生成。实现这种语言的关键是设计适当的单模态编码器来分割和表示单模态数据,以及一个协调的表示空间来关联和组合单模态特征以获得整体的多模态输入的含义,还有解码器来将多模态表示映射到预测(用于融合)或原始数据(用于翻译或生成)(Brainish: Formalizing A Multimodal Language for Intelligence and Consciousness, 2023†source)。

结果:这种转换机制为实现人工智能和意识提供了新的途径和理论基础。

从一开始,冯纽曼就对电路和计算机的电子元件产生了兴趣。他为了提高计算机元件的性能, 分析了它们的物理和化学属性。在他关于自动机理论的讲座中,他比较了计算系统中的生 物与人工元件在速度、尺度、可靠性和能量消耗以及二值决策所需要消耗的最小热能等特性。 (参见本文集第一部分的第四个讲座)正是由于这些物理学方面的工作,他才能够发明出新 的计算元件。

冯诺依曼的第一性原理

下面3个图是用DAllE生成的谐波发生器的示意图

OIG (1).jpgOIG (3).jpgOIG (4).jpg

冯诺依曼的自动机理论

之所以冯纽曼可以在很多不同的领域做出突出贡献,主要原因是他可以根据自己的兴趣把很 多完全不同的能力综合起来。他的超强理解和记忆能力可以很快地吸收、组织、保留和使用大量的信息。而广泛的兴趣又使他能够接触到很多领域的工作。他是一个解决各种困难问题 的高手(virtuoso),并且可以用他自己的方法深入分析,直到触及各种问题的本质。

他曾虚 心学习历史以及科学研究方法,并探讨它们与纯数学的关系。

他相信自动机的新逻辑将更类似于概率论、热力学和信息论。因此冯纽曼的自动机 理论从一开始就具有明显的跨学科特征。

他形式化地给出了两个自动 机理论的基本问题并初步进行了解答,这就是:一个可靠的系统是如何利用不可靠的元件构 造的?什么是一个自复制自动机的基本逻辑构成?第一个问题在他的文章“概率逻辑以及如 何由不可靠元件合成可靠的有机体”中,第二个问题则在本文集的第一部分的第五个讲座以 及第二部分进行了讨论。

冯纽曼通过比较当时最好的计算机与自然界中最智慧的生命得出结论:至少有三个因素可能 制约了工程师们建造更加强大的计算机的能力:可用元件的尺寸,这些元件的可靠性,以及 对计算元件如何组成复杂的逻辑结构的理论缺乏了解。冯纽曼关于元件部分的工作是对第一 个困境的解决,而他关于可靠性和自复制自动机方面的工作分别是对第二个和第三个局限的 挑战。在他的《概率逻辑:从不可靠组件合成可靠整体》的文章中,给出了两种克服元件不可靠性的方法:不是将这些元件变得更可靠,而是通过变换组合它们的方式使得计算机整体 变得更加可靠。他把他这部分的工作视作是一种概率逻辑,这也是沿着自动机逻辑方向迈出 的第一步。他关于自复制的工作也属于复杂自动机理论。他认为那些具有很大复杂性的系统中存在着定性的新规律,而这种新规律可以通过对强烈依赖于复杂性的自复制现象的研究而 获得。而且,我们知道自复制和自修复的联系非常紧密,因此对自复制现象的研究将有助于 我们解决可靠性的问题。

另外,还有两个相关的因素。首先,冯纽曼相信我们应该从那些可以被清晰描述的问题,甚至是我们熟悉的日常现象入手开始建立一门新科学,这些经验的积累可以进一步发展出一套 严格的理论去解释这些现象。他关于可靠性和自复制的问题就属于这一类。第二,冯纽曼相信复杂自动机的恰当理论将有助于解决计算机能力瓶颈的问题。他明确地指出,除非我们 有了一个关于自动机的足够深刻的理论,否则计算机的复杂度和能力就有一个极限,而我们 很难突破这个极限。

  1. 理论与实践

理解与记忆

两对概念内部之间相互促进和保持平衡

2.自复制自动机和自修复的紧密联系,而自修复可以动态的解决不可靠问题。

模拟与数字计算机是最重要的一类人工自动机,但通讯或 信息处理目的而造的其他的人造系统也包括在其中,如电话和收音机广播系统等。生物自动 机则包括了神经系统、自复制和自修复系统,以及生命的进化与适应等特性。

第一堂课 一般意义上的计算机

第二堂课 控制与信息理论

概述

McCulloch & Pitts 的神经网络

【接下来,冯纽曼讲解了“McCulloch & Pitts 的重要结论”,想象有一个具有若干输入和 唯一输出的黑箱。再选择两个时间点:t1和 t2,并确定从 t1到 t2何种输入组合会导致输出, 何种输入得不到输出。】不论你如何选择这些条件,总可以在黑箱里设计一套神经网络来实 现这些条件。这意味着神经网络在一般意义上是同符号逻辑等价的。这是一个事实,即任何 被设计出来的系统都可以用有限长度的描述来严格表示,因此他们是等价的。这里我不打算 证明它,因为任何形式系统的证明都是冗长且困难的。【这里简单说一下证明的方法,按照 冯纽曼所说,所有的开关函数(真值函数、布尔函数)都可以用确定延迟的神经网络来实现。 利用循环的方法,我们可以用神经元来实现任意容量的内存,并附加到以上的开关函数上。 这就相当于给一套符号逻辑加上了一根无限长的纸带,也就是实现了图灵机。因此,对于每 一台图灵机 M,总可以制造一套等价的神经网络,计算得到同样的数字】

确定延迟的神经网络?

冯纽曼在讲解这个结论时,提到了神经网络可以实现与符号逻辑等价的功能。这意味着神经网络可以模拟任何可计算的过程,实现任意复杂的逻辑计算。确定延迟的神经网络指的是具有固定的时间延迟的神经网络。

在神经网络中,每个神经元接收来自其他神经元的输入信号,并在一定的激活阈值下产生输出信号。这些信号在神经元之间传递时存在一定的延迟。在确定延迟的神经网络中,这种延迟是固定的,使得网络的计算过程在时间上具有一定的顺序性。这种顺序性使得神经网络能够进行顺序操作,类似于符号逻辑系统中的推理过程。

在冯纽曼的证明方法中,他提到可以通过循环方法实现神经元的任意容量内存,并将其附加到开关函数(真值函数、布尔函数)上。这就相当于给符号逻辑系统提供了一个无限长的纸带,从而实现了图灵机。因此,对于每一台图灵机,都可以构造出一个等价的确定延迟的神经网络,计算得到相同的结果。这表明神经网络在计算能力上具有通用性,可以实现任意复杂度的计算任务。

1.为什么神经元形成一个循环就可以保存信息2.用神经元开关函数是不是就是图灵机的中间的运算算法,而循环的内存是纸带?

  1. 神经元形成一个循环可以保存信息,这种现象通常被称为"循环神经网络"(Recurrent Neural Network, RNN)。在这种网络中,信息可以在神经元之间循环流动。具体来说,每个神经元的输出不仅影响下一个神经元,而且在下一个时间步骤也会反馈给自己。这种反馈机制使得神经元可以在时间上保持状态,也就是它们可以记住过去的输入。这种内存机制使得RNN非常适合处理时间序列数据,比如语音和文本。

  2. 你的理解是正确的。神经元的开关函数可以被看作是图灵机中间的运算算法,而循环的内存可以被看作是图灵机的纸带。在这种情况下,神经元的开关函数负责处理和转换输入数据(类似于图灵机的读写头),而循环的内存则存储这些数据,可以被看作是图灵机的无限长纸带。这就是为什么神经网络,尤其是循环神经网络,可以被看作是图灵完备的,也就是说,它们可以模拟任何图灵机。

神经元连接成循环,是可以记录某种状态,但这种记录的状态可以完全理解成有内存能力吗?

当神经元以循环的方式连接时,它们可以保存信息,这通常被称为"隐藏状态"。在一种特殊的神经网络架构中,即循环神经网络(Recurrent Neural Network, RNN),这种机制被直接用于处理序列数据,例如时间序列或者自然语言文本。因为在每个时间步,隐藏状态都能保留一些关于过去输入信息的内存,所以它能够对处理具有时间依赖性的问题特别有效。

然而,把这种隐藏状态理解为"内存"需要小心。在计算机科学中,"内存"通常指的是可以随机访问的存储设备,我们可以在任何时间读取或写入任何位置的数据。但在RNN中,隐藏状态并不支持这样的随机访问,其信息的获取和更新是通过时间步的前向传播来实现的。即,只有在给定前一时间步的隐藏状态和当前的输入后,才能得到当前时间步的隐藏状态。这种情况下,隐藏状态更像是一种"延迟"或者"历史"的内存,而不是传统意义上的随机访问内存。

另外,虽然RNN理论上可以记忆任意长的信息,但在实际应用中,RNNs往往会遇到所谓的"长期依赖"问题,即网络难以保留和利用过去很远的信息。这主要是因为在反向传播过程中,梯度可能会发生消失或爆炸,使得网络难以学习到如何利用这些远期的信息。为了解决这个问题,研究者设计了一些更复杂的RNN变体,如长短期记忆网络(Long Short-Term Memory, LSTM)和门控循环单元(Gated Recurrent Unit, GRU),它们通过引入更复杂的内部门机制,能更有效地保存和利用长期依赖信息。

除了随时读取上的差别,他能存取的对象,是状态state,而内存的存取对象可以有很多种数据,是不是这样?

是的,您的理解是正确的。

在循环神经网络(RNN)中,保存的对象通常被称为"状态"(state)或"隐藏状态"(hidden state)。这些状态通常是实数向量,代表了网络在某个时间步的内部状态,通常是对过去输入的某种编码。这种状态并不直接对应到任何特定的数据类型,而是网络学习到的一种用于完成其任务的信息表示。

与此相反,计算机内存中的数据可以有很多种形式,例如整数、浮点数、字符串、图像、音频、视频等。这些数据通常是具有明确意义和格式的,并且可以通过某种编码/解码过程转换为人类可理解的信息。此外,计算机内存允许我们在任何时间随机访问任何位置的数据,而RNN的隐藏状态则不能提供这样的随机访问能力。

因此,虽然RNN的隐藏状态在某种意义上可以被视为一种"内存",但它与计算机内存在功能和用途上有很大的不同。

网络学习到的一种用于完成其任务的信息表示,是不是它对于输入数据的分类或特征化的它自己的理解方式?

是的,您的理解是正确的。

神经网络(包括循环神经网络)的工作方式是通过学习从输入数据到输出数据的映射。在这个过程中,网络会学习到一种对输入数据的内部表示,这种表示捕捉了对完成任务有用的信息。这种表示通常是高度抽象的,并且不容易直接解释。然而,它们是网络如何理解输入数据的关键部分。这种信息表示在神经网络中通常是隐含在网络权重和激活函数之间的复杂互动中。

例如,如果我们在一个图像分类任务中训练一个神经网络,网络可能会在其内部表示中学习到与图像中的特定特征(如边缘、纹理、颜色等)相关的信息。这些特征然后被用来决定图像属于哪个类别。

在循环神经网络中,这种内部表示(即隐藏状态)还会捕捉到输入数据中的时间动态性。例如,如果我们在语音识别任务中使用RNN,那么网络的隐藏状态可能会包含有关当前语音信号过去几个时间步的信息,这对于理解和预测未来的语音信号非常有用。

【冯纽曼展示了如何建立一些样例网络。如上图,a 可以抑制 b,b 可以抑制 c,c 又可 以抑制 a。如果输入端被激发(箭头处输入),且抑制端(箭头处输入)没有激发,则神经 元进入激活状态。根据此规则,如果 a 和 b 都被激发,那么 α 会激发,而 β 不激发;如果 b 和 c 都被激发,那么 β 会激发,而 γ 不激发;并且,如果 a 和 c 都被激发,那么 γ 会激发, 而 α 不激发。冯纽曼利用这个例子来说明人类行为的不确定特性,比如 a 比 b 强,b 比 c 强, 照理说应该 a 比 c 强。但是在上面的神经网络中间,虽然 a 比 b 强,b 比 c 强,c 却又比 a 强。】

你提到的样例网络是冯纽曼在论文中给出的一个例子,用来说明神经网络可以实现一种非线性的逻辑关系,即**循环抑制**²。循环抑制是指三个或多个神经元相互抑制,形成一个稳定的循环状态,只有当其中一个神经元被外部输入激活时,才会打破循环,抑制其他神经元。这种逻辑关系可以用来解释人类行为的不确定性,比如你举的例子中,a比b强,b比c强,但c又比a强。这种情况在自然界中也很常见,比如石头剪刀布游戏。

要理解这个样例网络的工作原理,需要知道以下几个概念:

- **输入端**:指神经元接收外部输入信号的部分,也就是箭头指向神经元的连接。

- **抑制端**:指神经元发送抑制信号的部分,也就是箭头从神经元指出的连接。

- **激活状态**:指神经元输出信号为1(或正值)的状态。

- **抑制状态**:指神经元输出信号为0(或负值)的状态。

- **激活函数**:指神经元对输入信号进行加权求和后,通过一个非线性函数得到输出信号的函数。冯纽曼在论文中使用了一个阶跃函数作为激活函数,即当输入信号大于0时,输出为1;当输入信号小于等于0时,输出为0²。

根据冯纽曼给出的规则,如果输入端被激发(箭头处输入为1),且抑制端没有激发(箭头处输入为0),则神经元进入激活状态(输出为1);否则进入抑制状态(输出为0)。因此,可以根据不同的输入组合得到不同的输出结果,如下表所示:

| 输入 | 输出 |

| --- | --- |

| a=1, b=1, c=0 | α=1, β=0, γ=0 |

| a=1, b=0, c=1 | α=0, β=0, γ=1 |

| a=0, b=1, c=1 | α=0, β=1, γ=0 |

| a=0, b=0, c=0 | α=0, β=0, γ=0 |

不同层次的复杂性

我实际上正在用自己的方式解释一条非常漂亮的逻辑定理,这是由哥德尔曾经提出的一 条定理:从逻辑上说,对于一个对象的描述要比这个对象本身高一个级别。因此,渐进地说, 前者总是比后者要长。我觉得为了理解这种性质,必须运用上述定理,因为在你去深入研究 这件事情的时候,你已经触及到复杂度这个概念的本质。有理由怀疑,在一切模糊的、难以 定义的事物背后,都存在着复杂度渐近的性质(比如“看上去相似是什么意思?”),给人的 感觉是,不管你用多少文字,都没有办法把问题彻底描述清楚。这类事物就属于高复杂度的 情况,也就是实际去做,让机器实际去运行,反而比直接描述它要更快。因此,在这种情况 下电路本身的执行要比描述出电路所有的功能和可能的条件更快。 形式神经网络能够做任何你能用文字描述出来的事情,这个理念非常重要,在复杂度不太高的时候,这种处理方法能够非常大程度地简化问题。但是在复杂度很高的情形下,定理 所描述的情况则完全有可能相反,也就是逻辑电路反而比文字形容更加简单。

\==哥德尔说的描述比对象本身高一个级别,为什么呢?这个级别有事甚意思呢?冯诺依曼说的复杂情况下,本身比描述要简单,这是为什么呢?这不是和哥德尔的说法相悖了吗?

1.哥德尔说的描述比对象本身高一个级别,是指在一个形式系统中,对于一个对象(例如一个数学命题或一个数学结构)的描述,需要用到比对象本身更复杂的语言和符号。例如,如果我们想描述自然数的性质,我们需要用到一阶逻辑和皮亚诺公理。这个级别的意思是,描述的语言和符号的复杂度或表达能力。

冯诺依曼说的复杂情况下,本身比描述要简单,是指在一些高度复杂的系统中,用形式化的语言来描述系统的行为或规律,可能比直接观察或模拟系统本身更困难或不可行。例如,如果我们想描述一个神经网络的工作原理,我们可能需要用到大量的数学公式和算法。但是如果我们直接让神经网络去学习和执行任务,可能会更快更有效。

这不是和哥德尔的说法相悖了吗?不一定。哥德尔的说法是针对形式系统中的命题和证明的,而冯诺依曼的说法是针对复杂系统中的结构和行为的。它们并不完全是同一层次的概念。而且,哥德尔的定理只适用于包含初等数论的自洽的形式系统,而冯诺依曼的观点可能适用于更广泛的复杂系统。

2.首先,我们来理解哥德尔的观点。他的定理中,"对象的描述比对象本身高一个级别"的观点,源自他的不完全性定理。哥德尔的不完全性定理表明,在任何足够强大的形式化系统中,总会有一些陈述无法被系统内部证明为真或假,但在更高级别的系统中可以被证明。这就是"高一个级别"的含义:描述或证明是在系统的一种抽象、元系统级别上进行的,这种级别在某种意义上“看见”了系统本身不能看见的东西。

而冯·诺依曼的观点,可以理解为在实际操作中的复杂度问题。描述一个系统(例如一个计算机程序或者电路)的所有可能行为和状态,可能需要的信息量和处理时间要远远超过系统本身的运行。例如,你可以运行一个复杂的程序在几秒钟内得到结果,但如果你要完全描述程序的所有可能路径和结果,可能需要几个小时甚至更长时间。这就是冯·诺依曼所说的,复杂情况下,系统本身比描述要简单。

这两个观点并不矛盾。哥德尔的观点关注的是系统的逻辑和数学属性,特别是系统内部无法解决的问题。而冯·诺依曼的观点关注的是实际运行和操作的效率。在实际操作中,一个系统的运行通常比描述它的所有行为更为简单和快速。

有关记忆

图灵机

【接着冯纽曼说到了图灵关于有限自动机的结论:存在通用图灵机 AU,具有以下性质: 对于任何图灵机 A 和程序 I,存在模拟程序 IA,只要提供 IA 和 I 给 AU,AU 就可以模拟 A 的运 算,输出和 A 执行 I 得到的相同结果。】AU 具有模拟任何图灵机去执行任何指令的能力,哪 怕这个图灵机比 AU 本身要复杂得多也没关系。因为通用图灵机本身的复杂性不足,可以由 模拟器程序包含的内容来填补。这项研究的深刻之处在于,只要把通用图灵机恰当地制作出 来,它就能够完成任意复杂的工作,因为其他的各种需求可以通过编写程序来满足。但是, 只有当任意的图灵机 A 具有最起码的复杂度,从而能够实现通用图灵机的时候,它才能有这样的能力。换句话说,没有达到通用图灵机复杂度的系统,不管你给它写什么程序,都是 不可能完成某些工作的。但是一旦复杂性超越了某一个确定的阈值,只要给予适当的程序, 所有的自动机都能够相互模拟了。

【冯纽曼跟着解释,通用图灵机 AU 是怎么模拟任意一个图灵机 A 的。模拟程序 IA就像 一本对照词典一样,包括了所有 A 的状态和每一个符号的组合,说明在这个情形下,A 的下 一个状态是什么,在纸带上应该写入什么符号。AU 按照这本词典运行,就可以得到跟 A 一 模一样的输出了。】到此,我想指出,人类第一次具有了某种通用的工具,理论上说,只要 任何人能够做到的事,这种工具也能复现此过程。这里并没有无中生有,凭空制造复杂度, 因为程序还是得具体的写出来。而且,实现通用计算的这一过程也是基于严格的计算理论的, 亦即关于怎样描述对象以及如何在字典中间查阅条目并执行的过程。 不仅如此,图灵还发现了自动机的极限。也就是说,无法制造这样一种自动机,一台能够预测其他自动机在有限时间内是否能解决某个问题然后完成停机的自动机。换句话说,虽然你 可以制造能够模拟任何图灵机的通用图灵机,你却无法制造可以预测任何图灵机运行结果的 “预测机”。做过的事情可以重复,但是没有做过的事情,却没有办法预测。 以上结论同形式逻辑的结构本身具有深刻的联系。虽然在这堂课上不能深谈,我想说一下大概的意思,以便熟悉形式逻辑的人去研究。这一点跟类型论(theory of types)和哥德 尔定理有关,你可以在一个逻辑类型中间做任何可行的事情。但是一件事情是否可行这个问 题本身,却属于高一个层次的逻辑类型。我之前提过,低复杂度的东西,很容易预先判断它 的行为。但是对于高复杂度的形式逻辑对象,却很难提前预测它的行为,最好的办法就是把 它实际制造出来运行。在此情形下,一个问题的有效范围要比问题本身处在高一个层次的类 型。

通用图灵机可以被看作是一个可以变身为其它任意一台图灵机(甚至包括通用图灵机它自 己)的机器。只要给它输入适当的指令,它就可以原封不动地模拟其它图灵机(M,M’,M’’)的工 作。我们通常用的通用可编程计算机实际上就是通用图灵机,程序员给机器输入的程序就相当于 是任意一台特定的图灵机(例如求解 1+1 的值得图灵机)的描述。

通用图灵机能模仿任何哪怕是比自己更复杂的图灵机,1.是不是说明只要有足够复杂合理的结构,通用图灵机之间是没有区别的?2.是不是说明,模仿本身是一种表层的浅层的学习?

  1. 的确,通用图灵机可以模拟任意给定的图灵机及其输入,但它不能模拟具有自我描述能力的图灵机,包括它自己和其他通用图灵机。这是因为停机问题的不可判定性,即不存在一个算法可以判断给定的通用图灵机在给定输入上是否会停机。因此,尽管通用图灵机具有广泛的模拟能力,但仍然存在一些任务它无法完成。

  2. 关于模仿作为学习形式的性质,实际上,模仿涉及在不同层次的信息之间进行转换,这可能需要直觉、独创性、分析和创造力。例如,图灵的模仿游戏(也称为图灵测试)要求计算机在自然语言对话中模仿人类的智能和行为。这不仅仅是简单地复制或重复人类的言论,还需要理解、推理和创造力。因此,模仿学习并非仅仅是浅层学习,而是涉及更多复杂的认知过程。

通用图灵机本身的复杂性不足,可以由 模拟器程序包含的内容来填补。1.人是不是图灵机或通用图灵机?2.人达到了最基本的复杂度,即使预装系统有限(1.8GB左右?),也可以通过后天的学习填补大脑空间,从而完成更多的任务。但是如果本身和想要模拟的对象需要的模拟器程序大小相差太大,会不会出现小马拉大象的情况,本身的复杂性是不是也需要一定的更新?

1. 人是否是通用图灵机是一个哲学和科学假设的问题,没有确定的答案。有观点认为人的认知可以用通用图灵机建模,大脑本质上是执行心理程序的计算机。但也有观点认为人脑与数字计算机有本质差异,如并行性、可塑性、模拟处理和创造力等。还有观点认为人的思维可能超出图灵可计算性,如直觉、意识或自由意志。

2. 假设人是通用图灵机,人可以通过学习新程序或技能来更新其复杂性。但是,这并不意味着人可以克服通用图灵机的内在限制,如停机问题的不可判定性或逻辑的不完备性。此外,人学习或存储在大脑中的信息量可能受到实际限制,如记忆容量、处理速度或注意力。因此,人可能无法模拟任何其他通用图灵机或图灵机,特别是如果它们比人自己更复杂或更高效。

1.Sci-Hub | The human Turing machine: a neural framework for mental programs. Trends in Cognitive Sciences | 10.1016/j.tics.2011.05.007

→ 附件 PDF

2.(PDF) From Analog to Digital Computing: Is Homo sapiens’ Brain on Its Way to Become a Turing Machine? (researchgate.net)

→ 附件 PDF

3.https://www.aiforanyone.org/glossary/turing-machine

(我忘了1.8GB可以在哪里看到,也不确定准不准,问bing后给了我三个链接:

1.https://www.ncbi.nlm.nih.gov/books/NBK21134/

2.https://en.wikipedia.org/wiki/Human_genome

3.https://www.genome.gov/genetics-glossary/Gigabase

但我在第三个链接中看到“This analogy can help us appreciate the size of human genome, about 3.4 gigabases.”,我问bing到底哪个准,他说:

The question is about the discrepancy between the 1.8 GB and the 3.4 GB figures for the size of the human genome. According to the web page that the user provided, the 3.4 GB figure is based on the total length of DNA in a diploid human cell, which has two copies of each chromosome. The 1.8 GB figure is based on the compressed size of the haploid human genome, which has one copy of each chromosome. The compression is possible because the human genome contains a lot of repetitive sequences that can be eliminated without losing information. Therefore, both figures are correct, but they measure different things.)

补充材料:Arthur Burks 与 Kurt Godel 的通信

在课程最后一段中,冯纽曼提到了哥德尔的一条定理“你可以在一个逻辑类型中间做 任何可行的事情。但是一件事情是否可行这个问题本身,却属于高一个层次的类型。”因为编者不知道哥德尔曾得到过这样的定理,这段话显得十分费解。另外他在之前引用的有关哥 德尔的讨论(47 页),还包括冯纽曼的希克森研讨会上的文章,“自动机的一般和逻辑的理 论”(参见冯纽曼文集的 5.310-311),。所以我给哥德尔教授写信询问此事,不过我认为他给 出的答案是关于参考文献最模糊的解释。因此,编者把与哥德尔的通信稍作编辑,附在下面:

我的信件如下:

鄙人正在编注已故冯纽曼教授关于自动机原理的未完成手稿,在 1949 年伊利诺伊大学 的以及此前的希克森会议上,他都引用了您的著作,但我却查不到出处,因为有可能冯纽曼 生前曾同您谈及过相关问题,我冒昧给您致函,请求指点。

手稿的背景如下:冯纽曼当时在讨论视觉识别,他说可以把人的眼睛和神经系统看成一 部确定的有限自动机。他提出如下的可能,即描述这类自动机的行为的最简方式,是把自动 机的结构依样画葫芦地描述出来。这是令人信服的。但是我不能明白他接下来说的话:

在这个范围内,有可能实际对象本身就是它自己的最简单描述。这是说,任何用文字 或者形式逻辑来描述一个对象的尝试,都可能导致比对象本身更加复杂,牵涉到更多关系的 结果,也就是越说越复杂。现代逻辑研究中的某些结论暗示了,在遇到高度复杂的对象的时 候,这样的奇特性质反而是正常的。‛这里似乎提到了您的工作,鄙人随信附上全文,敬请 参阅。

在伊利诺伊大学的课上,冯纽曼也提出了类似的观点:视觉产生过程最简单的精确描述 方法,就是把大脑的视觉部分神经元连接罗列出来。他接下来说,对于形式逻辑的研究表明, 当自动机不太复杂的时候,对于自动机功能的描述要比自动机本身简单。但对于复杂自动机, 情况却相反。他这里指名道姓提到了您的定理‚我实际上正在曲解一条逻辑定理,但是这个 定理本身是非常漂亮的。这是由哥德尔曾经提出的一条定理:从逻辑上说,对于一个对象的 描述要比这个对象本身高一个级别。因此,渐进地说,前者总是比后者要长。我觉得为了 理解这种性质,必须运用上述定理,因为在你去深入研究这件事情的时候,你已经触及到复 杂度这个概念的本质。

此后,在叙述了图灵机以及图灵对于停机问题不可判定性的论述之后,他再次回到这个 问题上面。他说这些问题跟类型论和您的研究结果有着深刻联系。此处的录音记录有些乱, 我尽量保留了原文‚这一点跟类型论和哥德尔定理有关,你可以在一个逻辑类型中间做任何 可行的事情。但是一件事情是否可行这个问题本身,却属于高一个层次的类型。我之前提过, 低复杂度的东西,很容易预先判断它的行为。但是高复杂度的形式逻辑对象,却很难提前预 测它的行为,最好的办法就是把它实际制造出来运行。在此情形下,一个问题的有效范围要 比问题本身处在高一个层次的类型。

‛ 鄙人能够理解一个对象的描述要比对象本身高一个类型层次。但是,除此以外,我不明 白冯纽曼的意图何在。我有两个想法,但是似乎都不能够自圆其说。一是把哥德尔配数当作 一个公式的描述来对待。但是,至少在某些情况下,哥德尔配数的长度是可以小于公式的长 度的,否则自指的不可判定的公式就是不可能的了。另外一种可能的理解是同您 1936 年的 论文《关于证明的长度》中间提出的证明长度定理有关。有两个系统:S 和较大的系统 S1, 您的定理说:对于每一个递归函数 F,在两个系统下都存在一个可证明的陈述使得在这两个 系统下的最短的证明满足一个不等式,也就是在小系统 S 下的证明的哥德尔配数要比 F 作用 在大系统 S1 中间证明的哥德尔配数大。这符合冯纽曼说的结论,问题是结论正好相反:类 型越高,证明越短而不是越长。 冯纽曼教授的这段叙述令我十分迷惑不解,如您能不吝赐教,鄙人不胜感激。

哥德尔的复信如下:

我对于冯纽曼当时的意图,大致有一些概念,但是因为我从未和他谈及这些问题, 这仅仅是我个人的猜测。

我认为冯纽曼提到在下的定理的时候,并非是指存在不可判定的断言或者证明长度的问题。而是一个认识论上的事实,即语言 A 的完全描述是无法用语言 A 本身来给出的,这是 因为在 A 里面,没有办法定义句子的真假。这条定理才是包含算术的形式系统不可判定性的 真正原因。但在我 1931 年的论文中间没有提出这条定理,直到 1934 年我在普林斯顿的讲 课上才正式提出。同样性质的定理也由塔斯基于 1933 年提出。

上述定理清楚地表明,在某些情况下,相比对于机制本身,对机制会做什么的描述要 牵涉更多的东西。在这个意义上,它需要用更加抽象的术语来表达,也就是更高的层次。 但这仅仅是抽象的程度,同需要用到的符号数量没有关系。正如您所说的,符号数量和层次 高低可能是成反比的。

但是,如果从通用图灵机角度来看,冯纽曼的想法会变得更加清楚。对于图灵机,我 们可以说其行为的完全描述是无穷大的。因为既然不存在通用的停机判定方法,那么要描述 一台具体图灵机的行为,只有把其所有的状态枚举出来才行。当然,为了不陷入无限大带来 的困难,我们这里做了一个假定,即只有可判定的描述才是完全的描述。通用图灵机的两种 复杂度之比为无穷大,同时它又可以被当作其他各种有限机制的一种极限,这立即就导出了 冯纽曼的结论。

1.哥德尔猜测,冯纽曼指的不是证明长度,而是关于认识论的事实。

2.对于一个机制(或系统、对象)的描述,可能会比这个机制本身要涉及更多的内容,因此需要更高层次、更抽象的语言或符号来表达。但是,这并不意味着描述的符号数量要比被描述的对象多。这与冯·诺依曼的观点相一致,即对于复杂的自动机,描述其功能可能比自动机本身更复杂。(对于复杂的理解)

3.任何足够强大的数学系统,都无法证明其系统内部所有的命题。

系统无法证明其自身的一致性。

第三堂课 信息的统计理论

自动机的“韧性”

robustness或可“稳健性”

概率作为逻辑的扩展

我认为,这两种解释的区别,至少在拉普拉斯看来,是十分清楚的,他曾指出存在两种 不同的方式来看待概率:频率和逻辑方式【《A philosophical Essay on Probabilities》】。在近代, 经济学家凯恩斯也曾撰述概率方面的论文【《A Treatise on Probability》】,强调了两者之间的 区别,并以此作为他的理论基础。凯恩斯相当详细地分析了概率问题,并说明了除了传统的 频率解释以外,还可从逻辑的角度来解释概率。但他并没有试图把严格逻辑和概率区分开来, 仅仅提到,如果你观察一个事件 A 和 B 的序列,这个序列可以用一个具体的量“B 紧跟着 A 发生的概率”来刻画。这里同严格逻辑的唯一联系之处就是如果此概率等于 1,你可以说 A 导致 B 的蕴涵关系,如果概率是 0,那么 A 的发生就排除了 B 的发生。但是,当这个概率接 近 0 或者 1 的时候,你还是可以用一种模糊的方式进行推理。

严格逻辑可以看成是概率逻辑的子集,也就是可能性为0或100%时,可以无偏的往下推演。然而从概率逻辑的范围来看,0~100%,有多少逻辑能必然的落到整个光谱的两极呢?朴素的角度看,是不是应该绝大多数都处于两者之间的某个数呢?或者,这种概率数值的分布概率图会不会是均匀分布、正态分布或双峰分布呢?有时候,非常接近0或1的情况,也可以进行一种模糊的推理方式,即模糊逻辑。

对于连续随机变量,我们通常使用概率密度函数(probability density function, PDF)来描述其分布。概率密度函数在某个具体点的值并不能直接解释为该点发生的概率。相反,我们需要通过积分概率密度函数来计算某个范围内事件发生的概率。

概率密度函数的值只是表示了随机变量取该点附近的值的相对可能性,而不是绝对可能性。因此,一个概率为0的事件只是表示该事件在无穷多次重复试验中几乎不会发生,但并不排除它在某一次试验中发生的可能性。在连续随机变量情况下,单个点的概率测度为0(因为长度为0),这意味着具体点的事件发生概率为0。然而,这并不意味着该事件是不可能发生的。实际上,在连续随机变量的情境下,概率为0的事件仍然有可能发生。这是因为,在连续随机变量中,我们关注的是事件在一个区间内发生的概率,而不是某个具体点的概率。

例如,如果我们抛掷一个标准正方体骰子,那么它落在任何一个顶点上(不是面上)的概率都是0,但这并不意味着它永远不会落在顶点上。这种情况在量子力学中也有类似的例子,比如隧道效应就是一个概率为0但仍然可能发生的现象。

熵

冯纽曼说,香农的信息论是一种用来测量信道传输信息能力的计量理论。他介绍了冗余 度的概念,并指出通过冗余信息,我们可以实现纠错;这就像编辑校对原稿时候,不用询问 作者,就可以改正拼写等常见错误的道理一样。冗余度是“使得我们可能书写较长文章(比 如 10 页以上)的唯一原因”。换句话说,如果一种语言被压缩到了完全没有冗余的程度,那 么它也不适用于传输较复杂的信息,因为你完全没有办法知道其中的文字的对错。这是一个 原则问题,因此,我们使用的信息媒介的复杂度,和其传输信息所需要的冗余度之间,是有 联系的。

冗余,可以看作是效率和可靠性之间的权衡。 一方面,冗余会减少在给定空间或时间内可以传输或存储的信息量。 另一方面,冗余可以提高在嘈杂或不确定的环境中可以恢复或理解的信息的稳健性和质量。

如果自动机中间某一个部件太快了,其他部件跟不上;或者内存太小了;或者缓存和内 存的速度比例设置的太大,缓存不够用;这些情况都会导致效率损失,就好象一台热机因为部件之间的温差太大导致能量白白浪费的性质一样。这些我就不细讲了,总之,我相信热力 学同自动机的联系是非常紧密的。

第四堂课 大数之道

人脑与电脑的比较

读书笔记可输出