论可计算数及其在判定问题中的应用(2010哈工).doc

论可计算数及其在判定问题中的应用A.M.Turing1．计算机2．定义 自动机器 计算机 可循环数与不可循环数 可计算的数列和数3．计算机的例子4．微型桌面 更有深度的例子5．列举可计算的数列6．一般计算机7．一般计算机的详细描述8．对角线方法的应用9．可计算数的数组的例子10．一个大的可计算的数组的例子11．可计算数在其判定问题中的应用附录Endnotes：可计算的数可以简要描述为那些十进制形式可通过有限步骤来计算是实数虽然这篇论文表面上讲的是可计算数，但它也研究了可计算方程，无论整数、实数或可计算变量，等等这篇论文简单给出了可计算数、方程等之间的关系这会包括函数理论的发展和实变量用可计算数表示一个数，如果它是十进制形式，还可以被机器识别，它就是可计算的 在9.10中给出了一些关于所有数都是可计算的 的讨论其实，作者给出了一定大的数组都是可计算的它们包括，算术数学中的实数部分，Bessel函数中是实数部分的零，如x,e等然而可计算数不全包括可定义是数，其中一个例子就是能找到一个不可计算却可定义的数 即使可计算数组如此大，在许多方面它与实数集很相似从正确讨论的应用中，结论与Godel<1>的很相似，着都是有价值的证明。

在Alonzo Church的最近的一篇论文中介绍了“有效计算”的思想，它与作者“计数”的思想很接近，不过又定义的十分不同Church还探求了有关判定问题的结果有关“计数”和“有效计算”本质相同的证据，列在了附录中1． 计算机我们知道可计算数是那些十进制可以通过有限步骤计算的，不过我们需要更明确的定义 而计算机的需求是因为人类的记忆是有限的我们可以设想一个人将一个个实数输入一个只能存有限数q1，q2……qr的机器，将被叫做“m—配置”，这个机器被纸带供应，被分为“方格”（也叫做square），每次能生成一个符号某时只有一个方格叫做“r—th”，生成S(r)的符号我们就将它称为“扫描方格”，符号被称为“扫描符号”这样可以用机器来做计算，当符号被写下会形成数列或是数字，数列与数字都是十进制的可以计算的其余的记录全都用来记忆而正是这些记录我们才认为计算是可信任的这就是作者的关于书的计算的论点，下节会有关“machine机器”“纸带”和“扫描的”含义与理解2． 定义，解说1） 自动机器 如果这台机器的每个动作都完全由配置决定，我们就将这个机器叫做“自动机器”（或a—机器）因为一些原因我们会使用部分动作由配置决定的机器（选择机器或c—机器）。

当这样一台机器，任意的外部操作都会影响它的运行，没有外部操作它也根本无法运行这篇论文只研究自动机器2） 计算机 如果一台自动的机器包括两种符号，第一种（也叫数字）只包括0和1，其余的叫符号或第二种符号，那么这台机器就可称为计算机符号打印的子数列称为“机器计算的数列”二——十进制的数称为“机器计算的数” 纸带的符号和m—配置被称为完全配置机器上合纸带上的改变叫做机器的一个步骤3） 循环和不循环的机器 如果一台机器从来不写下多于有限个第一类数（0和1），那么它就叫做可循环的机器，否则就叫做不可循环的机器4） 计算数列与数 如果一个数列可以被不可循环的机器运算，那么它就是可计算的3． 计算机的例子如果一个数列010101……一个机器有4个m—配置“b”“c”“z”“e”而且可以打印“0”和“1”机器的表现为描述以下桌面，“R”表示“机器正在扫描从上次扫描处右侧”，“L”表示从左侧，“E”表示擦除，“P”表示打印就像这样配置表现b无P0,Rcc无Ree无P1,Rzz无Rb 一个难一点的例子，我们要计算数列001011011101111011111……会引入“o”“p”“q”“f”“b”打印“e”“x”“0”“1”。

可替换方块中的一个被称为F-方块，其余的称为E-方块，E-方块的特点是易于擦除F-方块中的数应该是连续的，而在它运行到结尾之前是没有空格的两个F-方格之间有一个E-方格E-方块的明显的可以满足符号打印在E-方块上的需要如果一个符号J-是在E-方块的s的右边然后S和J会被称为标记为I这个进程可以打印为I，I会被记为J（或S）和I记在一起4． 微型桌面几乎所有的机器都在用对应的进程，而且，一些机器用了许多链接这些工程包括复制符号数列，比较两个数列，擦除已给形式的所有符号，等等这样我们可以考虑用m-配置用于基于缩写有关的桌面这些都是“变量”的自然意义通过吧希腊文转化为德文，我们就获得了m-配置我们可以用基干桌面造出微型桌面基干桌面应该与微型桌面一样：它们不是必须的 我们可以说这个机器会有m-配置q和所有可得到的m-配置，会成为一个可以把c转化成p(c)的m-配置代替这样就会得到qYp(q),p(p(q)),p(p(p(q))) 如果我们用q来代替C，用r代替B，用x代替I，我们会得到一个完整的m-配置，f(q(r,x))的桌面，f就被称为m-配置方程，或m-方程 可采纳的用来代替的都是m-方程的m-配置机器的符号。

那些用明显的列举出来：他们可能包括表示像p(e,x)一类的符号，他们也一定需要m-方程如果我们不支持明确的列举，而是简单的陈述，机器用当然的m-配置，而且所有m-配置获得的通过用m-方程代替m-配置然后它会在qYp(q),p(p(q)),p(p(p(q)))，就像m-配置然后我们的就是这样，我们给出了m-配置关于机器的名称，大部分m-配置会用m-方程来表示我们也给出了它相对应的基干桌面，所有我们想要的是为m-配置完成机器桌面这样会得到基干桌面通过反复操作来替代 更深远的的例子 用符号“/”表示机器进入m-配置5． 列举可计算的数列一个可计算的数列0是决定于一个机器，可以计算0的机器对它的描述这样，数列001011011101111……就为一个桌面所决定，而且实际上，任何一个可计算的数列都能被这样一个桌面描述把这些桌面放到一个标准形式中会很有用开始让我们假设这个桌面与给出的第一个桌面一样，就是说，那个在运算中的项一般是下列中的一个：E,R:E,L:Pa:Pa,R:Pa,L:R:L:或没有项这个桌面一般会可以通过介绍更多m-配置成这个形式现在，让我们给一些数m-配置，称它们为q1,q2……qn。

最初的m-配置常被称为q1，我们也给符号S1,S2……Sm一些数，其中特殊的是，空格=S0，0=S1，1=S2，这个桌面的线现在形式……qisjPsk,Lqm(N1)qisjPsk,Rqm(N2)qijspskqm(N3)像下面的线：Qi sj E,R qm被写成： Qi sj PSO,R qm并且像这样的线： Qi sj R qm可以被写成qi sj psj,R qm用这种方法我们将桌面上的每条线都缩减为（n1）(n2)(n3)三种形式中的一种 从（n1）中的每条线来看，我们建立了q1,si,sk,l,qm的表达方式；从(n2)中的每条线来看，我们建立了qi,si,sk,r,qm的表达方式；从(n3)中的每条线来看，我们建立了qi,sj,sk,nqm的表达方式，来为机器从桌面上建立他们，并且用分号分开它们用这种方法我们得到了一个完整的关于机器的描述在这样的描述中，我们可以将qi替换为“D”后加一个”A”字母重复i次，并且sj替换为”D”后加个”C“重复j次这种关于机器新的描述可以被称为”标准描述“（SD）它完全由字母”A””C””D””L””R””N”和符号”；“组成。

最后，如果我们将”A”替换为L””C”替换为“Z”“Ｄ＂替换为＂３＂＂Ｌ＂替换为”４“，”Ｒ＂替换为“５”，“Ｎ＂替换为”６“，并且”Ｊ替换为“７”，我们就有了一种关于机器的描述，这种描述的形式是阿拉伯数字这种用数字的整数来代替的形式可被称为机器的数字性描述（ＤＤ．Ｎ＂决定了”ＳＤ“并且机器的构造是唯一的Ｄ．Ｎ是Ｎ的机器可被描述为Ｍ（Ｎ）对每个可计算的数列，对应至少一种描述数字，同时对于没有描述数字的，对应着多于一种可计算的数列因此，可计算的数列和数字是可列举出来的下面，找出＆３中机器Ｉ的描述数字当我们重新命名Ｍ－配置时，它的桌面就变成了：ｑ１　　　　　　　　　　ｓｏ　　　　　　　ｐｓ１，Ｒ　　　　　　　　ｑ２ｑ２　　　　　　　　　ｓｏ　　　　　　　　ｐｓｏ，Ｒ　　　　　　　　ｑ３ｑ３　　　　　　　　　ｓｏ　　　　　　　　ｐｓ２，Ｒ　　　　　　　　ｑ４ｑ４　　　　　　　　　ｓｏ　　　　　　　　ｐｓｏ，Ｒ　　　　　　　　ｑ１其他的桌面可以由上面两个不同的线相加得到，例如；ｑ１　　　　　　　　ｓ１　　　　　　ｐｓ１，Ｒ　　　　　　　　　ｑ２我们最初的标准形式是：ｑ１ｓｏｓｓ１ｒｑ２；ｑ２ｓｏｓｏｒｑ３；ｑ３ｓｏｓｏｒｑ４；ｑ４ｓｏｓ２ｒｑ１；标准的描述是：ＤＡＤＤＣＲＤＡＡ；ＤＡＡＤＤＲＤＡＡＡ；　　　　　　DAAADDCCRDAAAA;DAAAADDRDA;数字性描述是：31332531173113353111731113322531111731111335317并且可以写成如下:31332531173113353111731113322531L1173111133531731323253117一个可循环计数机器的数字性描述的数字可被叫做一个满足的数字。

在&8中表明还没有通常的办法来判定一个给定的数字是不是满足的6普遍性的计算机发明一种独立的机器，用来计算任何可计算的数列是可以实现的如果我将这部机器在开始时配置一纸带，用来记录某些可计算机器M的S.D，那么我能计算出和M相同的数列首先，我们假设我们有一部机器M‘，它将记录F-方格，继续完成机器M的构造这可能于P235表达形式是一样的，用第二种描述，将所有符号都写到一条线上或者，我们可以将这种描述(&5)变换为将每个M-配置替换为“D“后加字母A重复合适的次数并且A和C的次数与&5中被选的数字一致，这样的话，特别的0被DC替代，1被DCC替代，空格被D替代这些替代都将实现，在配置被完全结合在一起之后，正如（C）如果我们首先做替代的话难度会增大在每个完成的配置中，所有的空格都必须用D来替代，因此完整的配置不能被一个有限的符号来表示如果在&3中，机器2的描述中，我们用DAA替代0，DCCC替代E，DAAA替代Q，那么（C）列就变成了DA：DCCCDCCCDAADCDDC:DCCCDCCCDAAADCDDC:………..(C1)（这就是F-方格上符号的列）不难知道，如果M能被制造，那么M‘也能计算M‘的方式可以被制定，依赖于它本身内部的地方有计算规则；每部都能进行下去，根据这些规则。

我们只需要将这些比率认为能可取的并且可交换的或者，我们有与普通机器很相似的东西第一件就是：目前M‘机器还没有出版的图形我们可以修正它，通过出版完整配置在每个连续对之间的图形，他将出现新的配置而不是旧的那么（C1）变为DDA:0:0:DCCCDCCCDAADCDDC:DCCC……….(c2)这并不能很明显的看出Ｅ－方格为必须的“粗糙工作“留足了空间，但事实就是这种情况在冒号之间的字母数列被表示为（Ｃ１），可能用完整的配置的标准描述当字母被数字所代替，如＆５中，我们将得到完整配置的数字性描述，我们将它称为描述性数字。