配图是精髓( ﾟ∀ﾟ)

jmjp

挖！

https://y.music.163.com/m/song/20045591

除了排序后列表这种最基础的数据结构，算法界常用的数据结构还有树（Tree），图（Graph），哈希表（Hash Table，又名散列表），队列（Queue），栈（Stack），链表（Linked List）等。

其中，树可以被看做是满足特殊规则的图，队列和栈可以被看做是所带函数更加受限的列表。

但这不代表树就是比图更加“低端”，或者更加没用。原因主要有二：第一，人们更容易将树与一些应用联系起来，为这些应用设计或实现树的算法，并将图与另一种应用联系起来；第二，一个树常常比同等大小的图有更少的排列组合可能性，使得其在被筛选时复杂度更低，这就像瑞士军刀固然功能性多，但匕首用起来更干脆利落。

每一个数据结构都有一堆对应的，利用该数据结构特性的算法。因为各种数据结构的性质，有些适用于图的算法也可以用于树，适用于队列的算法也可以用于列表。

但可以用≠高效，毕竟如果不是要创造出对应的高效算法，何必多此一举创造出规则更特殊的数据结构呢？

在此，po不多赘述其他数据结构和对应算法，尽管知道它们对于了解计算机科学（和通过大厂笔试）来说是非常重要的。一个合格的程序员在看见一个问题的那一刻，心里就应该有几种备选的数据结构与算法方案。

对于这些数据结构和算法的研究也从未终止过，并且这些研究很多都在为所谓的PNP问题以及更难的类似问题做出贡献。由于这个问题非常难以表述，请读者自行查阅。理解PNP问题需要先理解常见算法与数据结构→集合论→图灵机与可计算性→逻辑与SAT问题→库克理论。

数据结构大家族就像马戏团，每个成员都以特殊——有时候看起来甚至可笑——的形式出现，但都有其不可替代的意义。

时隔半年的更新Σ( ﾟдﾟ)

感动cn

http://music.163.com/album/1603461

编程语言

人们对程序员的定义就是“能够使用编程语言达成预期目的的职业”。并且，计算机科学研究中非常神奇的一点就在于99%的研究成果可以直接用编程语言来复现。这种高效的理论-产品转化率也是计算机科学蓬勃发展的原因之一。

那么什么是编程语言？在了解编程语言之前，我们需要先知道什么是计算机科学范畴下的符号与语言。

>符号
语言由符号组成。从集合论的领域来说，我们称一个符号是它从属于的符号集Σ中的一个元素，符号集Σ是由符号组成的集合（听不懂就请先自行了解集合论基础理论）。

例如对于二进制语言来说，Σbinary={0, 1}。0与1为符号，Σbinary为二进制符号集。类似的，英语符号集包含了26个英语字母和英语标点符号。

符号集容纳了一个语言可能使用到的所有符号（文字）。一个由符号集Σ中符号构成的，任意长度排列组合叫做语句。例如，1001是二进制语言的一个语句，Rock&Roll是英语的语句。

在离散数学中，我们不是一笔一划地“写下”一个语句，而是从符号集中按顺序选择一个个符号来形成语句。

如果没有语法（grammar）限制，一个非空符号集所能构成的语句的集合Σ*中有无限个元素，并且所有只含某符号集内符号的排列组合都是该符号集的语句。但很可惜，我们有语法来规范什么语句是合法的，什么语句是非法的。

>语法
语法是任何将一个符号集中符号的排列组合分割为合法语句与非法语句的筛选规则。我们定义满足语法的语句是合法的，否则是非法的。一般来说，我们并不讨论非法的语句，除非我们想利用某种规则将其改成合法的。

例如，我们可以定义一种二进制语言的语法是必须要以1为开头，那么100是一句合法语句，而0110则不是。

语法也可以很复杂，特别是自然语言的。例如根据复杂的英语语法，I is fishes是不合法的，而Am I a fish?则是合法的。

一个语言可以有自下而上的数套语法一齐规范。例如在自然语言处理（Natural Language Processing，NLP）的理论中，英语有三重语法，分别是词义（lexical），句法（syntactic）和语义（semantic）。例如I am a waorker中含有错误拼写的词语，不符合词义语法。I a worker am并没有按主谓宾的结构排列，不符合句法。而I am a TV则在语义上没什么道理，只适合在前卫摇滚中出现。

我们想要有一种方式来系统化/自动化地判断一种符号的排列组合是否满足某语法。为此，我们发展/利用了许多理论，例如状态机（State Machine），无上下文语法（Context Free Grammar，CFG）等。利用基于诸如此类的理论所创造工具，程序可以自动判断你写的句子是否符合某种语法，甚至还能纠错。

>语言
我们定义语言为一套符号集与其对应的语法。取决于人们的需求，语言可以是二进制数字，中文，说出来的话，手语，音乐，图片，分子的理论运动轨迹（考虑到量子的离散性）等等等等，因为它们都是符号的排列组合，都可以用符号的排列组合来精准定义。

对于语言这种抽象概念的广泛存在，一些最早将前卫要素引入金属乐的人已经意识到了。音乐也可以是图片，或者文字。Images & Words.

强大的po

支持

https://y.music.163.com/m/song/1809425

>符号，数学与功能

我们已经知道了在程序员的语言学中语言是由符号集和语法组成的。接下来，我将简单聊聊为何如此定义语言，语言是如何做到编程的，编程语言是如何与我们想用其实现的功能所对应的。

在此之后，我们会深入到编程语言本身，讲述编程语言需要具有的性质，并由底层开始简述编程语言的运行原理（这一段只是为了让我不至于忘了下面该讲什么）

>哥德尔不完备定理，图灵机与可判定性问题

这一段涉及到一些与编程语言无关，但发展出现在我们使用的编程语言符号学的理论的历史。如果对此不感兴趣，可以跳过其中的大多数段落，包括这个回复的下面的所有内容。我会在编程语言强相关段落的开头加上###以让大家有选读的选择。

一切的一切都要从一个问题谈起，那就是可判定性问题（Entscheidungsproblem）。

1928年，大卫•希尔伯特（现代数学之父）与威廉•阿克曼（算法与大数领域的著名数学家）提出了可判定性问题：是否有一算法，输入任何命题，都能根据命题的普遍正确性输出“是”（该命题在任何情况下都正确）和“否”（该命题不是在任何情况下都正确）。

如果这样的算法存在，那么可以说所有数学问题都可以被证明或者证伪。不管是“素数是否有无限个”还是“是否任何大于2的偶数都能写作两素数之和”，都是可以在人类智慧的努力下推论出“是”或者“否”的正确答案的。

然而，哥德尔在1931年证明：只要命题基于正式的数学语言（准确来说，基于含皮亚诺算术公理的自洽形式系统），都存在无法被证明或证伪的可能性。这个定理被称为哥德尔不完备定理。

在计算机科学中有一个与可判定性问题类似的问题，叫做决定性问题（Decision Problem）。决定性问题泛指输入数据，根据数据输出“是”或者“否”的问题。例如输入一个数，输出这个数是否是素数；或输入一个列表，输出这个列表是否从小到大排列。

图灵与邱奇跟着在1936年几乎同时分别独立证明了并非所有决定性问题都（在图灵机的范畴下）存在对应的解决算法，他们使用的方法与哥德尔类似。

不管怎么说，数学与计算机的世界都因为这两个证明而变得残缺了。因为不管如何努力，总存在我们探寻的问题根本就不可解的客观可能性。

接下来，我会先讲哥德尔是如何通过符号与数字的转化来证明可判定性问题的不完备，再讲图灵是如何通过图灵机这种基于符号与集合的数学系统来证明世界上存在不能用算法解决的决定性问题的。

虽然哥德尔和图灵等人从根本上否定了许多科学家所做事业可能存在的意义，但这两个定理还是有一点好处的。

那就是，对于一个问题，科学家们可以理直气壮地说出：I Don't Know!

>哥德尔数与哥德尔编码（上）
接下来我们会讲到哥德尔不完备定理的证明。虽然这是二十世纪最重要的定理之一，但它的证明并不难，只需要从另一个角度（语言的角度！）来看待数学。

假设一数学系统符号集，其中每一个符号都代表数学论证中所要用到的符号，例如0，=，+，*，（，）x，y等。虽然数字是无限的，但这个符号集是有限的，因为其中含有一个符号s叫做“后继”，定义为对于数字n，ns=n+1。0s=1，0ss=2，用诸如此类的方式可以构建所有自然数。

这个数学符号集中符号构成的语言就是数学命题。例如语言“0=0s”的含义就是“提出一个命题，该命题为：0是等于1的”。自然，这个命题是假命题。

可判定性问题就是想要知道是否所有的命题都可以被证明是真命题或者假命题。而哥德尔接下来就要证明有些命题不能被证明成真命题或者假命题。

###假设这个涵盖所有论证所需的数学符号集里的每个符号都被给予了一个不一样的独特正整数编号。例如符号“=”的编号可以是5，符号“0”的编号可以是6，符号“s”的编号可以是7。编号到底是什么无所谓，只要不同的符号不一样即可。为了简便，我们定义一个函数g(x)，输入符号x，输出该符号的哥德尔数。例如g(s)=7。

###给定一个数学命题，即数学符号集中符号e的排列组合l=e1e2e3...，其中en指第n位的符号 例如语言0=0s中e1为符号0，e2为符号=，e3为符号0，e4位符号s。

###有了函数g，我们可以为这个数学命题定义一个独特的哥德尔编码，定义给予编码的函数为G。G(l)=2^g(e1) * 3^g(e2) * 5^g(e3) * 7^g(e4) * ...。即，给定l，G每次按顺序从左向右依次拿取l的i个元素，并向结果乘第i个素数的g(ei)次方。

###例如，G(0=0s)=2^g(0) * 3^g(=) * 5^g(0) * 7^g(s)=2^6 * 3^5 * 5•6 * 7^7=200,120,949,000,000。通过这种方法，对于所有数学命题l，我们都能找到对应的独特哥德尔编码G(l)。用同样的方式，对于所有符号集，我们都可以设计这样的函数G，使得符号集中的每一个语言都可以有与该符号集中其他语言不同的哥德尔编码。

###我们也可以反过来从哥德尔编码倒推出其对应的语言。200,120,949,000,000除以2可以整除6次，结果为3,126,889,828,125，所以对应语言中第一位的哥德尔数是6，对应符号0。3,126,889,828,125除以3可以整除5次，结果是12,867,859,375，所以对于语言中第二位的哥德尔数是5，对应符号=...

###G是一个单射函数：对于所有语言，G都可以推导出自然数。如果一个语言符号集中有无限多个符号，那么这个语言的G函数是满射的（这也代表它是双射的），对于所有自然数，都有一个对应的语言l使得G(l)等于这个自然数，自然数和语言一一对应。

###如果你看不懂这一段，没有关系，你只要知道语言与数字本质相同。这是哥德尔给我们的启发。

>>No.63267984
很有意思啊，不知道你有没有看过数学女孩的书，里面也有许多类似的观点

https://y.music.163.com/m/song/666448

>哥德尔数与哥德尔编码（下）

接下来就是哥德尔不完备定理证明的重头戏：

定义函数sub(a, b, c)，这个函数输入的a代表一个数学命题l所对应的哥德尔编码G(l)，b代表一个符号b，c代表某符号x的哥德尔数，c=g(x)。这个函数的效果是输出一个新的命题，这个新的命题是将旧命题l中所有符号x替换成符号b所产生的。

例如，假设根据某哥德尔数排列方案，g(x)=10。sub(G(x=y), 0, 10)的输出是G(0=y)，我们将命题中哥德尔数为10的符号“x”替换成了符号“0”。

这个函数是可以通过因式分解很简单实现的。如何实现呢？各位可以自己思考一下如何输出更改后的哥德尔编码。

有了这个函数，我们定义一个数学命题：“哥德尔编码为sub(x, x, 10)的数学命题无法被证明”。也就是说，给定一哥德尔编码为某未知数x的数学命题，将这个数学命题中哥德尔数为10的符号（即“x”）替换为符号“x”（实际上，在此时，这毫无作用）后得到的命题无法被证明。

毫无疑问，在一个成熟的数学系统中，上面所述的数学命题是可以被表示成哥德尔编码的。我们不需要知道这个哥德尔编码是多少，只需要知道其存在就可以了，我们假设这个哥德尔编码是n。

根据n，我们再定义另外一个（也是最后一个）数学命题：“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”。定义这个数学命题的哥德尔编码为m。

sub(n, n, 10)将哥德尔编码n对应的命题中所有出现的，哥德尔数为10的符号x变成了n。

哥德尔编码n对应的命题为“哥德尔编码为sub(x, x, 10)的数学命题无法被证明”。将这个命题中的x替换为n之后，输出的对应命题为“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”。我们仅仅是把x这个符号替换成了n。

“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”这个命题是不是有点眼熟？没错，这个命题是我们定义为哥德尔编码为m的命题。也就是说，m=sub(n, n, 10)，同时，m对应的命题等价于“哥德尔编码为m的命题无法被证明”。

请问，m可以被证明？如果m可以被证明，那么我们证明了m无法被证明，显然，如果m可以被证明，那么一个悖论产生了：我们证明了一个东西无法被证明。

所以，m无法被证明。然而，m存在，因为我们可以构建出m。也就是说，在任何成熟到足以产生m对应命题的数学系统中，存在无法被证明的命题。

这就是哥德尔不完备定理：所有可以构建m，换言之，足够成熟的数学系统都存在无法被证明的命题。换言之，不是所有的数学命题都能被证明。换言之，数学家证明某些命题的行为可能是无用功。

In other words, please be true. 这句期望虽然很美好，却无法实现。

>>No.63670885
没有，搜了一下应该是类似的证明

( `_っ´)📚

>>No.63783434
数学女孩的作者还写过另一名为《程序员的数学》，也是很接近科普的，文字风格很像楼主，能让人心静下来。但都更偏向于数学。打字到这的时候突然想起刚刚过去的昨天是10.24，祝我们程序员节快乐。

突然想起马雷也学计算机ﾟ ∀ﾟ)ノ

哥德尔不完备定理看到一半忽然发现是不是通俗化之后的版本就是理发师悖论( ﾟ∀。)搜了一下好像还真是