离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
102-哥德尔编码
Loading...
From the course by Peking University
离散数学概论 Discrete Mathematics Generality
146 ratings
From the lesson
形式语言与自动机：图灵机与计算理论
Meet the Instructors
陈斌副教授
北京大学
[音乐] 嗨，欢迎回来。
下面呢我们就来试图来解决 这个停机问题。
肯定你会说，这个图灵机 它的规则那么多，而且千变万化，我可以任意的组合这些规则，
我怎么样才能穷尽这些图灵机，然后有一个一般性的方法去判定它这个停机的问题呢？
当然我们说你 去这么做的话，肯定是非常困难的，你看它本身这个符号体系就是
非常的这个复杂的，那但是呢我们
曾经在我们这门课上一直跟大家强调的一点就是
你如果面临一个新问题，你可以试图用老问题去解决新问题，
那是怎么样解决呢？就是找到老问题到新问题
建立一种同构，或者叫建立一种一个对应的一个关系， 一旦这个同构或者说变换建立好了以后，
我们就可以试图用解决老问题的方法来解决一个新问题。
那么在解决这个图灵机的 停机问题上这个方法也是一样的被应用的，
那个哥德尔呢想出了一个办法叫做哥德尔编码，
这个编码呢它是看到说我们可以把任何的这个形式语言 编码变成一个自然数的集合。
因为形式语言呢是字符串的集合， 而字符串是千变万化的，我是用什么样的字符或者说有多少
字符，这个字符集的大小这个都千变万化，
但是呢自然数的集合它可是非常确定的，人们对于自然数的研究非常的彻底，
当然也不能说就解决了所有的问题了， 至少呢我们在自然数的研究上，在数论的研究上
也前进的步伐还是比较，比较深入的。
那么这样呢就可以把这个语言上的运算 就变成了自然数的运算，比如说关于字符串的运算，
字符串是连接，那就变成了自然数的加法或者说其它的
什么其它的运算，那就是两个代数结构之间的一种 同构的一种关系。
那么而且呢我们就把由于形式语言作为符号系统
而形成的而构成的这种形式系统，它上面的这个问题就可以变成数论上的问题，
数论上的问题，关于素数啊，关于因式分解啊，关于其它的一些数论上的一些问题， 那同样的，我们由这个
字符串所构成的这个规则，那么规则所构成的图灵机，图灵机作为一个形式系统，
它的停机问题，是不是能够停机，那这个问题， 如果经过这样的一系列的变换，最终呢也可以变成一个数论上的问题，
是吧，那么当然我们还记得前面，最早第一个部分的时候， 我们说到数理逻辑里边，对于命题演算啊，谓词演算，
我们把它变换成这个真实函数，那么很多问题迎刃而解。
而且呢在讨论形式系统的时候有一个miu系统，
是吗？那这个我想大家可能印象还是比较深刻，如果你不太记得，你可以返回去再看一下。
对于miu系统，我们说mu这个字符串在不在这个集合里，
那么穷尽了这个miu系统本身的方法很难做到，最终呢我们是怎么解决的呢？
把miu变成了自然数集合。
最终呢我们发现，这个mu变成自然数是30。
那这样呢，通过数论上的一些，这个 定理，就明确的说这个mu是不属于这个字符串集合的。
那么这个问题也得到了很好的解决。
所以呢接下来我们就是说 看，怎么把图灵机变成一个自然数的集合，这就是哥德尔编码。
那么它的整个过程呢，首先我们在进行编码之前，
介绍几个必要的函数，我们先顶一个函数p(n)，
那么p(n)呢定义为第n个素数，这个n大于0，所以第n个素数呢， 比如说第一个素数是2，就这样，2，3，5，7，11，13，是吧，
所以呢p(1)等于2，p(2)等于3，这样子的， 那么我们知道呢，有几个这个事实，
第一个事实呢，素数是有无限多个的，所以呢这个p(n)呢， 它不会有说某一个自然数放进去p(n)没有值，
它不会，任何一个自然数放进去，那么p(n)呢它都会有值，都会有第n个素数，
然后来跟它对应，素数是有无限多个的。
第二个呢，是根据因式分解的问题，就是任何的这个 正整数，它都能够唯一地写成素数的乘积，
而且这个乘积呢是有唯一的，就是，这样呢，比如说6，它是等于2乘以3，
或者说这个 12，它等于2乘以2再乘以3，2的平方再乘以3。
那么而且这种分解的这种最终的样式它是唯一的，它不能够
表示成两组不同的素数的乘积，它是不会，所以这是唯一的能够写的乘积。
那么有了这两样之后，我们就可以对形式系统进行编码，对于这个语言来进行编码。
我们说语言L它是A芯的一个子集。
那么A呢，它是一个有n个字符的这么一个字符集，a1，a2...an。
那么我们从这个语言L当中提出一个，任何一个字符串w，
那么w呢它的长度为k，长度为k。
那么am1，am2...amk这样子的，它有这么长，
那么我们其中的这个mi， 就是w当中第i个字符在字母表当中的这个序号。
比如说这个w第一个，第一个字符，它是字母表当中的第二个字符的话，
那么这个m1呢就等于2，那么如果说它第二个 字符am2呢，它是字母表当中的
第五个字符，那么这个m2这个，就等于 5，这样。
那好，这个哥德尔编码呢就是这么一个公式。
G(w)等于，它是一个连乘，它是一个连乘，因为我们说
它可以唯一地写成素数的乘积嘛，每一个，每一个这个正整数， 所以它的连乘呢是把这个k个，这个进行连乘，
k个字符，那么它是pi，就是第n个，第i个素数，
i等于1到k，那么它就是有n个这个，有k个素数这么连乘，
那么每一个素数呢，它都有一个指数， 都有一个指数，这个指数呢就是这个
第i位个这个字母，它这个字符 在字符表里头它排的第几位
，它就是 几次幂，对吧，那么这个呢就是p(i)mi，然后呢把这个所有的
指数都连乘在一起，就称为哥德尔编码。
好，这个讲解这个公式呢是不太容易懂，我们来看看例子，
比如说这个例子当中，A呢它有四个字符，a，b，c，d，
那么这个四个字符的序号呢就是1，2，3，4，对吧，第一个字符是a， 第二个字符是b，第三个字符是c，第四个字符就是d，
那这样的，我们把这样的一个字符串进行编码，accdb dd，它包含了7个字符，
那么这个长度为7，那就有7个素数的这个指数进行连乘，
然后它是分别呢是，第一个素数，2，3，5，7，11，13，17，
那么这有，一共引用到了7个素数，然后每一个素数呢都加一个指数，它的几次幂，
这个次幂呢，是跟这个字符在字母表当中的这个位置是有关的，比如说，第一个字符是
a，那么它是第一个字符，所以呢是2的一次方， 那么c是第三个字符，所以它第二个呢是3
的三次方，然后呢第三个字符是c， 所以呢它是5的三次方，然后呢是7的四次方，
11的二次方，13的四次方，和最后一个d，那么就是17的四次方。
那当然这是一个非常大的数了，那么只是
它仅仅只是四个字符的字符集里头，一个长度为7的一个这么一个 字符串。
那最终呢，它会等于这样的一个，这么大的一个数。
当然 这个数的大小，在我们理论的讨论当中是没有关系的，它只要
不管你有多大，它都是有限的，对吧，所以我们，其实 并不需要说真实地去讨论某一个数它是等于什么，
我们只要讨论这个哥德尔编码，它这么一个函数，G(w)这个函数是如何运作的就行。
那这样呢我们发现呢，就是说一个字符串，它可以通过这个G(w)，编码成一个自然数，
那么反过来呢，我有这么一个自然数，也能够反推回去， 还原成一个字符串，那这样呢，它们就会有
一个建立一个一一对应的关系，当然这是一个单射的一个关系，并不是任何的 这个自然数反过来它都能够变成字符串，但是任何一个字符串
都能够通过哥德尔编码，变成一个自然数。
那么这里头呢就有一个重要的结论， 既然有哥德尔编码，它可以从它那得到一个重要的结论，
也就是说如果一个字符表A它是可数的， 也就是说字符表当中包含的字符，要么这个字符数
是有限的，要么呢它是无限的，但是呢它是一个自然数的子集，
你无穷子集也没关系，也就是说所谓的可数，就是说这个集合它可以对应自然数的一个子集，
有限集或者是无穷集，那么如果字母表A是可数的，那么A上的所有的形式语言，
就是它能够构成的所有的形式语言，就是A芯的子集， 那么这个L，每个L，它都也都是可数的，
也都是可数，因为呢在形式语言总可以通过哥德尔编码，变成一个自然数的一个子集，
所以呢它也是可数的，所以呢我们就通过哥德尔编码就把所有的
这个形式语言都变成了自然数的集合。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
