No.60413427 - 科学
计算机导读从摇滚开始无名氏No.60413427 只看PO
2023-12-04(一)01:21:43
ID:22b93o1
这是一个从零开始的计算机学教程。教程里不会出现太过于深奥的内容，而是鼓励肥哥们根据串内的推荐自行学习。这个串只起到初步解释和导读的作用。
为了让计算机学更加有趣，也为了满足我的摇滚癖好，计算机和摇滚会在这个串里有机地结合起来，毕竟学习时听听音乐不也挺好嘛(ゝ∀･)
无标题无名氏No.63247282
2024-07-28(日)21:26:58 ID: 22b93o1 (PO主)
https://y.music.163.com/m/song/1809425
>符号，数学与功能
我们已经知道了在程序员的语言学中语言是由符号集和语法组成的。接下来，我将简单聊聊为何如此定义语言，语言是如何做到编程的，编程语言是如何与我们想用其实现的功能所对应的。
在此之后，我们会深入到编程语言本身，讲述编程语言需要具有的性质，并由底层开始简述编程语言的运行原理（这一段只是为了让我不至于忘了下面该讲什么）
>哥德尔不完备定理，图灵机与可判定性问题
这一段涉及到一些与编程语言无关，但发展出现在我们使用的编程语言符号学的理论的历史。如果对此不感兴趣，可以跳过其中的大多数段落，包括这个回复的下面的所有内容。我会在编程语言强相关段落的开头加上###以让大家有选读的选择。
一切的一切都要从一个问题谈起，那就是可判定性问题（Entscheidungsproblem）。
1928年，大卫•希尔伯特（现代数学之父）与威廉•阿克曼（算法与大数领域的著名数学家）提出了可判定性问题：是否有一算法，输入任何命题，都能根据命题的普遍正确性输出“是”（该命题在任何情况下都正确）和“否”（该命题不是在任何情况下都正确）。
如果这样的算法存在，那么可以说所有数学问题都可以被证明或者证伪。不管是“素数是否有无限个”还是“是否任何大于2的偶数都能写作两素数之和”，都是可以在人类智慧的努力下推论出“是”或者“否”的正确答案的。
然而，哥德尔在1931年证明：只要命题基于正式的数学语言（准确来说，基于含皮亚诺算术公理的自洽形式系统），都存在无法被证明或证伪的可能性。这个定理被称为哥德尔不完备定理。
在计算机科学中有一个与可判定性问题类似的问题，叫做决定性问题（Decision Problem）。决定性问题泛指输入数据，根据数据输出“是”或者“否”的问题。例如输入一个数，输出这个数是否是素数；或输入一个列表，输出这个列表是否从小到大排列。
图灵与邱奇跟着在1936年几乎同时分别独立证明了并非所有决定性问题都（在图灵机的范畴下）存在对应的解决算法，他们使用的方法与哥德尔类似。
不管怎么说，数学与计算机的世界都因为这两个证明而变得残缺了。因为不管如何努力，总存在我们探寻的问题根本就不可解的客观可能性。
接下来，我会先讲哥德尔是如何通过符号与数字的转化来证明可判定性问题的不完备，再讲图灵是如何通过图灵机这种基于符号与集合的数学系统来证明世界上存在不能用算法解决的决定性问题的。
虽然哥德尔和图灵等人从根本上否定了许多科学家所做事业可能存在的意义，但这两个定理还是有一点好处的。
那就是，对于一个问题，科学家们可以理直气壮地说出：I Don't Know!
无标题无名氏No.63783174
2024-09-15(日)19:23:37 ID: 22b93o1 (PO主)
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. 这句期望虽然很美好，却无法实现。