下载文档原格式
理论计算机科学中的图灵机图灵机是理论计算机科学中的一个重要概念。
它被认为是能够计算任何可计算问题的最基本的计算机模型。
理解图灵机对于对计算机科学的学习和研究都至关重要。
一、图灵机的定义和原理图灵机是由英国数学家图灵提出的一种计算模型。
它包括一个有限控制器和一条无限长的纸带。
纸带被划分为一系列的单元格，每个单元格上可以写上一个字符。
控制器通过读取纸带上的字符和控制器内部的状态来进行计算。
它可以进行有限的计算，而且可以处理无限长的输入。
在图灵机模型中，所有的操作都是基于读取和写入单元格上的字符来进行。
图灵机具有非常简单的结构，但它却能够计算出任何可计算问题。
二、图灵机的应用图灵机能够计算出任何可计算问题，因此它在理论计算机科学中有着非常重要的应用。
它被用于证明计算机科学中的许多重要问题，例如停机问题和可计算性问题。
通过证明一个问题是不可计算的，我们可以得出它是无法用计算机解决的。
这对于计算机的设计和实现都有着重要的指导意义。
此外，图灵机还被广泛应用于计算机语言和自动机理论的研究中。
我们可以使用图灵机来描述计算机语言的语法和语义，并且使用它来定义自动机模型。
这在编程语言的编译、解释和分析中都有着广泛的应用。
三、图灵机的限制尽管图灵机是一种非常强大的计算模型，它仍然存在着一些限制。
其中最明显的一点是图灵机的速度。
尽管图灵机能够计算出任何可计算问题，但某些问题可能需要非常长的时间才能得到结果。
例如，计算出一个长文本的哈希值可能需要几分钟，而对于一个复合的问题，甚至需要几个世纪才能计算得出。
此外，图灵机还无法解决某些问题，例如非计算问题和不规则问题。
这些问题之所以无法用图灵机解决，是因为它们没有确定的方法来解决它们。
这些问题是无法用算法来解决的，并且需要人类直接进行解决。
四、结语图灵机是理论计算机科学中最重要的概念之一。
它被认为是能够计算出任何可计算问题的最基本计算机模型。
通过图灵机的研究，我们可以深入理解计算机科学的基本原理，理解计算机能力和限制。
世界最难的8道数学题数学可以是一个难以理解的学科，有时这些问题看起来根本超出了我们的理解能力。
有些数学问题可能是我们现实生活中所面临的最艰苦的挑战之一。
本文介绍了世界上最难的8道数学题，它们构成了数学界极具挑战性的最高峰。
第一个数学题叫做“吉布尔猜想”，它是由法国数学家阿尔贝吉布尔在1850年提出的。
该问题的目的是检查任意有界区域（由圆构成的区域）中是否可以完全用四边形来覆盖。
上至现在，该问题仍不能被证明。
第二个数学题叫做“莱布尼茨猜想”，是由挪威数学家安德鲁莱布尼茨提出的。
该猜想认为，任何一个自然数都可以写成四个素数的平方乘积。
自从莱布尼茨猜想于1849年提出以来，它就没有能证实过。
第三个数学题叫做“哥德巴赫猜想”，它是由德国数学家基尔斯特哥德巴赫提出的。
该猜想是指任何一个大于2的自然数都可以被写成两个质数的和，因此任何一个偶数都可以表示成两个相等的质数之和。
自从哥德巴赫提出猜想之后，科学家们仍在努力证明它的真实性。
第四个数学题叫做“孪生猜想”，它是由英国数学家萨姆霍夫曼和美国数学家爱德华奥尔特支提出的。
该猜想提出，任何两个质数之差都不可能小于17。
虽然现在有现成的证据来支持孪生猜想，但它还未被完全证实。
第五个数学题叫做“大定理”，它是由法国数学家安东尼玛丽安德烈约瑟夫拉格朗日在1835年提出的。
该定理认为，任何一个大于1的正整数都可以用有理数的乘积表示出来。
经历了数百年的研究和推敲，大定理被英国科学家安德鲁乔叟于1887年证明。
第六个数学题叫做“千佛拉定理”，它是美国数学家安东尼肖普在1600年代提出的。
千佛拉定理规定，一个多项式的系数可以表示成一个多项式的乘积。
千佛拉定理被证明是有可能的，但直到1986年，它才被数学家证实为正确的。
第七个数学题叫做“图灵机”，它是由英国数学家托马斯图灵在1936年提出的。
图灵机有一些极具挑战性的问题，它们要求一台机器执行一系列的复杂的计算，以实现一定的智能。
NOIP2009年普及组初赛题目及答案解析一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）1、关于图灵机下面的说法哪个是正确的：（D）A.图灵机是世界上最早的电子计算机。
B.由于大量使用磁带操作，图灵机运行速度很慢。
C.图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D.图灵机只是一个理论上的计算模型。
【解析】所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。
有一个机器头在纸带上移来移去。
机器头有一组内部状态，还有一些固定的程序。
在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
2、关于计算机内存下面的说法哪个是正确的：（B）A.随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B.1MB内存通常是指1024*1024字节大小的内存。
C.计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D.一般内存中的数据即使在断电的情况下也能保留2个小时以上。
【解析】A项：RAM不是位置随机，而是随时访问。
所谓“随机存储”，指的是“当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。
”B项：1MB=1024KB,1KB=1024BC项：计算机内存包括严格来说包括只读存储器（RAM）、随机存储器（ROM）和高速缓存（CACHE）。
如果不严格来说只包含只读存储器和随机存储器。
D项：内存中的数据断电立即丢失。
3、关于BIOS下面说法哪个是正确的：（A）A.BIOS是计算机基本输入输出系统软件的简称。
B.BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C.BIOS一般由操作系统厂商来开发完成。
P NP NPC三者问题阐述1）”P对NP问题”是什么意思？首先说明一下问题的复杂性和算法的复杂性的区别，下面只考虑时间复杂性。
算法的复杂性是指解决问题的一个具体的算法的执行时间,这是算法的性质；问题的复杂性是指这个问题本身的复杂程度，是问题的性质.比如对于排序问题,如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息,则排序问题的复杂性是O(nlgn)，但是排序算法有很多，冒泡法是O（n^2），快速排序平均情况下是O(nlgn)等等,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。
问题的复杂性不可能通过枚举各种可能算法来得到，一般都是预先估计一个值，然后从理论上证明。
为了研究问题的复杂性，我们必须将问题抽象，为了简化问题,我们只考虑一类简单的问题，判定性问题，即提出一个问题,只需要回答yes或者no的问题。
任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A 到B是否有长度为1的路径？从A到B是否有长度为2的路径?…从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。
如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。
P类问题就是所有复杂度为多项式时间的问题的集合.然而有些问题很难找到多项式时间的算法(或许根本不存在)，比如找出无向图中的哈米尔顿回路问题，但是我们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确。
比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他是否是哈米尔顿回路（只要看是不是所有的顶点都在回路中就可以了)。
这种可以在多项式时间内验证一个解是否正确的问题称为NP问题.显然,所有的P类问题都是属于NP问题的，但是现在的问题是,P是否等于NP?这个问题至今还未解决。
写这篇文章，是想尝试回答学习图灵机模型中遇到的三个问题：1) 为什么图灵机有不可判的问题？2) 为什么强大的图灵机会不停机？3) 为什么图灵当初要设计图灵机？图灵机（Turing machine）是英国数学家阿兰·图灵（Alan Turing）于1936年设计的一种抽象机器，用于定义和模拟计算（computing）。
图灵机虽然构造简单，但却及其强大，它能模拟现代计算机的所有计算行为，堪称计算的终极机器。
然而即便是这个终极机器，也有令它无能为力的问题，这便是第一个要回答的问题：为什么图灵机有不可判的问题？首先明确什么是图灵可识别（Turing recognizable）和图灵可判定（Turing decidable）。
图灵机的识别对象是语言，图灵可识别当然不是说图灵本人能识别的语言（照这样说汉语可能是图灵不可识别的~），事实上这只是简称，全称应该是图灵机可识别语言（Turing machine recognizable language）和图灵机可判定语言（Turing machine decidable language）。
一台图灵机在读取一个串后可能进入三种状态：接受、拒绝、循环，如果图灵机进入循环状态，那它将永不停机。
现在假设有语言A，如果能设计出一台图灵机M，对于任意字符串ω，如果ω∈A，那么M读取ω后会进入接受状态，那么A是一个图灵可识别语言。
注意这个定义对于ω不属于A的情况没有做出限制，所以M读取到不属于A的ω，那么它有可能拒绝，也有可能循环。
图灵可判定语言的要求更严格，它要求对于语言A能设计出一台图灵机M：如果ω∈A，M 进入接受状态；否则进入拒绝状态。
如果一个语言是图灵可判定的，总能设计出一台图灵机，能在有限步数内判定一个字符串是不是属于这个语言。
如果一台图灵机对所有输入总是停机，那么称它为判定器（decider）。
然而第一个问题指明一定有所有判定器都不能判定的问题，要证明这一点，得从康托（Georg Cantor）说起。
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute, 简称CMI）在千禧年大奖难题中收录。
P/NP问题中包含了复杂度类P与NP 的关系。
1971年史提芬·古克(Stephen A. Cook) 和Leonid Levin 相对独立的提出了下面的问题,即是否两个复杂度类P和NP是恒等的（P=NP?）。
P 和NP复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定型图灵机上在多项式时间内找出的问题的集合。
很可能，计算理论最大的未解决问题就是关于这两类的关系的:P和NP相等吗?在2002年对于100研究者的调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。
对于正确的解答，有一个$1,000,000美元的奖励。
NP-完全问题(或者叫NPC)的集合在这个讨论中有重大作用，它们可以大致的被描述为那些在NP中最不像在P中的。
(确切定义细节请参看NP-完全)理论计算机科学家现在相信P, NP,和NPC类之间的关系如图中所示，其中P和NPC类不交。
假设P ≠ NP的复杂度类的图解.如P = NP则三个类相同.简单来说，P = NP问题问道：如果是/不是问题的正面答案可以很快验证，其答案是否也可以很快计算？这里有一个给你找点这个问题的感觉的例子。
给定一个大数Y,我们可以问Y是否是复合数。
例如，我们可能问53308290611是否有非平凡的因子。
回答是肯定的，虽然手工找出一个因子很麻烦。
从另一个方面讲，如果有人声称答案是"对，因为224737可以整除53308290611",则我们可以很快用一个除法来验证。
图灵机工作原理图灵机是一种理论上的计算模型，由英国数学家艾伦·图灵于1936年提出。
它是一种抽象的计算设备，能够模拟任何可以通过算法计算的问题。
图灵机的工作原理主要包括输入、状态转换和输出三个基本部分。
首先，图灵机接受输入。
输入是指由输入符号构成的无限长的纸带，纸带上的每个符号都属于有限的字母表。
图灵机的读写头可以在纸带上移动，并能够读取当前位置的符号。
这些输入符号代表了问题的初始状态，图灵机需要根据这些输入符号进行计算和处理。
其次，图灵机通过状态转换来处理输入。
图灵机在内部有一个状态转换表，根据当前状态和读取的输入符号，图灵机可以根据状态转换表中的规则进行状态转换。
这些状态转换规则包括了读取当前符号后的下一步动作，如写入新符号、移动读写头的位置或改变内部状态等。
通过不断的状态转换，图灵机可以模拟出复杂的计算过程。
最后，图灵机输出结果。
当图灵机完成状态转换并停止时，纸带上的符号就代表了问题的计算结果。
图灵机可以通过读取纸带上的符号来输出最终的计算结果。
图灵机的工作原理可以用简洁的数学模型来描述，这种模型包括了输入符号、状态转换表和内部状态等重要元素。
通过这些元素的相互作用，图灵机能够模拟出任何可以通过算法计算的问题。
这种抽象的计算模型为计算机科学的发展提供了重要的理论基础，对于计算机算法和程序设计具有重要的指导意义。
总的来说，图灵机的工作原理是基于输入、状态转换和输出这三个基本部分的。
通过这些部分的相互作用，图灵机能够模拟出任何可以通过算法计算的问题，这为计算机科学的发展提供了重要的理论基础。
图灵机的工作原理不仅对计算机科学具有重要的指导意义，同时也为人工智能和机器学习等领域的发展提供了重要的思想参考。
第十六届全国青少年信息学奥林匹克联赛初赛试题一. 单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）1.2E＋03表示（）。
A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制位组成。
A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。
A.P∨(﹁P∧Q) ∨(﹁P∧﹁Q)B.Q∨(﹁P∧Q) ∨(P∧﹁Q)C. P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)D.P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)4.Linux下可执行文件的默认扩展名为（）。
A.exeC.dllD.以是都不是5.如果树根算是第1层，那么一棵n层的二叉树最多有（）结点。
A.2n-1B.2nC.2n+1D.2n+16.提出“存储程序”的计算机工作原理的是（）。
A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（）也成立。
A.YXZB.ZXYC.XYZD.XZY9.前缀表达式“＋3×2＋5 12”的值是（）。
A.23B.25C.37D.6510.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。
而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。
于是，为了提高系统整体的执行效率，在CPU中引入了（）。
A.寄存器B.高速缓存C.闪存D.外存11.一个字长为8位的整数的补码是11111001,则它的原码是（）。
A.00000111B.01111001C.11111001D.1000011112.基于比较的排序时间复杂度的下限是（），其中n表示待排序的元素个数。
A.O(n)B.O(n log n)C.O(log n) d.O(n2)13.一个自然数在十进制下有n位，则它在二进制下的位数与（）最接近。
写这篇文章，是想尝试回答学习图灵机模型中遇到的三个问题：1) 为什么图灵机有不可判的问题？2) 为什么强大的图灵机会不停机？3) 为什么图灵当初要设计图灵机？图灵机（Turing machine）是英国数学家阿兰·图灵（Alan Turing）于1936年设计的一种抽象机器，用于定义和模拟计算（computing）。
图灵机虽然构造简单，但却及其强大，它能模拟现代计算机的所有计算行为，堪称计算的终极机器。
然而即便是这个终极机器，也有令它无能为力的问题，这便是第一个要回答的问题：为什么图灵机有不可判的问题？首先明确什么是图灵可识别（Turing recognizable）和图灵可判定（Turing decidable）。
图灵机的识别对象是语言，图灵可识别当然不是说图灵本人能识别的语言（照这样说汉语可能是图灵不可识别的~），事实上这只是简称，全称应该是图灵机可识别语言（Turing machine recognizable language）和图灵机可判定语言（Turing machine decidable language）。
一台图灵机在读取一个串后可能进入三种状态：接受、拒绝、循环，如果图灵机进入循环状态，那它将永不停机。
现在假设有语言A，如果能设计出一台图灵机M，对于任意字符串ω，如果ω∈A，那么M读取ω后会进入接受状态，那么A是一个图灵可识别语言。
注意这个定义对于ω不属于A的情况没有做出限制，所以M读取到不属于A的ω，那么它有可能拒绝，也有可能循环。
图灵可判定语言的要求更严格，它要求对于语言A能设计出一台图灵机M：如果ω∈A，M 进入接受状态；否则进入拒绝状态。
如果一个语言是图灵可判定的，总能设计出一台图灵机，能在有限步数内判定一个字符串是不是属于这个语言。
如果一台图灵机对所有输入总是停机，那么称它为判定器（decider）。
然而第一个问题指明一定有所有判定器都不能判定的问题，要证明这一点，得从康托（Georg Cantor）说起。
康托最大的贡献可能是创建了现代集合论，他认为某些不同的无穷集合有不同的大小。
1891年，康托发表了一篇只有5页的论文，证明实数集的基数大于自然数集，并在这篇论文中提出了传说中的对角线方法（方法虽然巧妙但很简单，wiki上有我就不赘述）。
图灵机的不可判定问题便需要借助对角线方法。
而实数集“大于”自然数集这个事实，可以这么想：“无限×无限”比“无限×有限”大。
每个自然数是有限的，集合是一阶无限，自然数集就是一阶无限；相较之下，一个实数是一阶无限，集合又是一阶无限，那么实数的集合就是二阶无限。
这个一阶二阶只是我个人的说法，关于不同集合之间的大小关系，康托提出连续统假设，即希尔伯特第一问题，认为不存在一个基数绝对大于可数集而绝对小于实数集的集合，不过这跟今天的话题没有关系，不再展开。
回到正题：图灵机。
图灵机能够识别语言，而图灵机本身当然也可以由语言描述。
什么是语言？给定一个字母表∑，一个{[由∑中的字母组成的序列]的集合}就是∑上的一个语言（为了消除歧义，算式可以加括号，语言当然也可以）。
必须清楚这些概念中哪些是有限的，哪些是无限的：一个语言包含的字符串数可以是有限的也可以是无限的，但一个字母表上的所有语言的数目是无限的，而语言中任意一个字符串的长度是有限的。
首先要证明的是：一个字母表上所有语言构成的集合不仅是无限的，而且是不可数的。
这里需要借助无限二进制序列的集合来帮助证明。
一个无限二进制序列（即{0,1}组成的无限序列）是一阶无限，那么这些序列组成的集合就是“无限×无限”，可以通过对角线方法证明无限二进制序列是不可数的，也可以将实数集的元素唯一地映射到无限二进制序列集合。
用后者的方法，可以这样建立二者之间的映射：二进制序列每4个为一组，用8421BCD码编码，4位对应实数中的一位，再用1111表示小数点，这样每个实数总能映射到一个唯一的二进制序列，既然实数集不可数，那么无限二进制序列也不可数。
接下来证明，{无限二进制序列的集合B}与（任意字母表）{∑上的所有语言组成的集合L}是同样规模的，仍然通过建立映射的方法。
设∑上所有字符串的集合按字典序排序成∑*={s1, s2, s3, ...}，L中的每个语言A都对应一个二进制序列b：如果si∈A，bi=1；否则bi=0，这样的序列称作A的特征序列。
举个例子，如果∑={a,b}，A是所有包含b的串构成的语言，则A的特征序列b如下：∑*={a, b, aa, ab, ba, bb, aaa, aab,...}A ={ b, ab, ba, bb, aab,...}b = 0 1 0 1 1 1 0 1 ,...反之，每个二进制序列b也能对应一个唯一的语言，所以L与B等势，又因为B是不可数集，所以{∑上的所有语言组成的集合L}也是不可数的。
好，明确了所有语言构成的集合是不可数的之后，我要回答下面这个问题：为什么图灵机集合是可数的？（reserve：哥德尔配数法）从图灵机的定义入手，图灵机是1个7元组（Q，∑，Γ，δ，q0，qaccept，qreject）。
每一台图灵机总是由有限个字符编码而成：1) 有限的状态集Q。
2) 有限的输入字母表∑。
3) 有限的带字母表Γ。
4) 有限的转换函数δ。
5) 1个起始状态q0。
6) 有限个接受状态qaccept。
7) 有限个拒绝状态qreject。
若上述每个元素都用二进制编码表示，任意一台图灵机都只需要有限个二进制位。
再将这些二进制串按照字典序排列，就可以得到一个{图灵机集合}->自然数集的一一对应。
好，给定一个字母表∑：[∑上的所有语言]的集合<=>[二进制无限序列]的集合<=>实数集<=>不可数集[所有图灵机]的集合<=>自然数集<=>可数集有不可数个语言，却只有可数个图灵机，语言的集合“大于”图灵机的集合，所以从本质上证明了必然存在图灵机不能识别的语言。
推论：必然存在图灵机不能判定的语言。
理由是图灵可判定语言的集合不会大于图灵可识别语言。
图灵可判定语言要求更严格，所以应该存在这样的语言：它是图灵可识别的，但同时不是图灵可判定的。
事实确实如此，图灵自己就给出了一个：A={<M, ω> | M描述一台图灵机，且M描述的机器接受ω}首先证明A是图灵可识别的（形式化证明太过繁琐，这里只给出很高层次的证明）。
设通用图灵机U这样运行：U接受参数<M, ω>，它可根据图灵机M的描述模拟M的行为，并在虚拟的M上计算ω。
如果M接受ω，那么U进入接受状态；否则拒绝。
依据定义以及通用图灵机的存在性，U能识别A，所以A是图灵可识别的。
证毕。
顺着这个证明走下去，如果M本身遇到输入ω时会陷入循环，那么模拟M的U也会陷入循环，所以U不是判定器。
如果U知道M在ω上不停机，那么它可以进入拒绝状态，问题是它不知道。
那么能判定A的图灵机存在吗？我们就假设存在H，使得：1）若M接受ω，则H(<M,ω>) =接受2）若M不接受ω，则H(<M,ω>) =拒绝根据H的定义，无论M接不接受ω，H总能停机。
进一步再假设有图灵机D，以H为子程序，接受一个描述图灵机的串<M>，在H上运行H(<M,<M>>)，并返回相反的结果：1）若H(<M,<M>>)=接受，则D(<M>)=拒绝2）若H(<M,<M>>) =拒绝，则D(<M>)=接受也就是说，如果一台图灵机M接受描述它自身的串<M>，那么D(<M>)进入拒绝状态。
构造这样一台奇怪的D是为了让它做下面这件事情，现在对D输入描述它自己的串<D>，看看会发生什么：1）若D接受<D>，即H(<D,<D>>)=接受，则D(<D>)=拒绝2）若D拒绝<D>，即H(<D,<D>>) =拒绝，则D(<D>)=接受到底是接受还是拒绝呢？兜了一个圈子，D绕回原地，产生了矛盾。
所以D是不存在的，所以H也是不存在的，语言A不可判定。
证毕。
上述证明比较绕，我用一阶逻辑再改写一遍。
命题：1）P：存在语言A的判定器H2）Q：存在以H为子程序的图灵机D（描述见上）已知条件：1）P→Q：如果有H，总能设计出D2）┐Q：D是不存在的（证明见上）证明：1 P 假设2 P→Q 已知条件3 Q 1,24 ┐Q 已知条件5 ┴推出矛盾6 ┐P 假设不成立上面的证明中，图灵机D的构造简直是神来之笔，图灵怎么想到的？虽然之前的证明没有直接给出不可判定的语言，但已经从数量上证明有图灵机不能判定的语言，由于判定器的要求更严格，所以可以推断所有判定器构成的集合小于所有语言构成的集合。
这是个与“实数集的势大于自然数集”类似的命题，所以应该能用类似的方法——对角线方法证明。
好，尝试一下。
康托构造映射表格时，表格的每一行由一个自然数表示这是第几行，每一列也由一个自然数标识列数，对角线法构造出来的实数实际上是一行，然而这一行却和每一行都不一样。
刚才的证明我们看到，图灵机集合是可数集，可将其对应自然数，标识表格的每一行，那么每一列用什么标识呢？怎样让列数与行数相等呢？行和列的交叉处是什么呢？自然数/实数的例子中，每一行由一个自然数对应一个实数，在这个问题中，行由图灵机标识了，那么不难想到，每一行应该是一个语言。
语言又该如何表示？下面依次回答这些问题。
列应该用什么来标识？在对角线方法中，表格的行列数一致，行和列都用自然数集标识。
那么首先可以想到既然行用图灵机标识，那么列也可以用图灵机标识。
但是这样的话行列交汇处就没什么意义了，试问随意挑选的两台图灵机之间能擦出什么火花？脑子再转一下，图灵机与图灵机之间没有什么一般化的关系，图灵机识别的是语言，是字符串，那么将标识列的图灵机换成描述图灵机的串，既保持了行列数一致性，又让行列交汇处有了非平凡的意义！即，用M1, M2, M3...标识第1行、第2行、第3行……再用描述图灵机的字符串<M1>, <M2>, <M3>...标识第1列、第2列、第3列……行列交汇处就填入accept 或reject，表示一台图灵机是否接受描述某一台图灵机的串！这样，每一行刚好也就是一个语言，每一个部分的意义都正好是我们想要的。
<M1><M2><M3><M4>……M1acceptrejectrejectrejectM2rejectrejectacceptrejectM3acceptacceptrejectacceptM4rejectacceptrejectaccept…………为构造对角线准备的表格走到这一步，离结果就很近了。
