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

论可计算数及其在判定问题中的应用A.M.Turing1．计算机2．定义自动机器计算机可循环数与不可循环数可计算的数列和数3．计算机的例子4．微型桌面更有深度的例子5．列举可计算的数列6．一般计算机7．一般计算机的详细描述8．对角线方法的应用9．可计算数的数组的例子10．一个大的可计算的数组的例子11．可计算数在其判定问题中的应用附录Endnotes：可计算的数可以简要描述为那些十进制形式可通过有限步骤来计算是实数。虽然这篇论文表面上讲的是可计算数，但它也研究了可计算方程，无论整数、实数或可计算变量，等等。这篇论文简单给出了可计算数、方程等之间的关系。这会包括函数理论的发展和实变量用可计算数表示。一个数，如果它是十进制形式，还可以被机器识别，它就是可计算的。在9.10中给出了一些关于所有数都是可计算的的讨论。其实，作者给出了一定大的数组都是可计算的。它们包括，算术数学中的实数部分，Bessel函数中是实数部分的零，如x,e等。然而可计算数不全包括可定义是数，其中一个例子就是能找到一个不可计算却可定义的数。即使可计算数组如此大，在许多方面它与实数集很相似。从正确讨论的应用中，结论与Godel1的很相似，着都是有价值的证明。在Alonzo Church的最近的一篇论文中介绍了“有效计算”的思想，它与作者“计数”的思想很接近，不过又定义的十分不同。Church还探求了有关判定问题的结果。有关“计数”和“有效计算”本质相同的证据，列在了附录中。计算机我们知道可计算数是那些十进制可以通过有限步骤计算的，不过我们需要更明确的定义。而计算机的需求是因为人类的记忆是有限的。我们可以设想一个人将一个个实数输入一个只能存有限数q1，q2……qr的机器，将被叫做“m—配置”，这个机器被纸带供应，被分为“方格”（也叫做square），每次能生成一个符号。某时只有一个方格叫做“r—th”，生成S(r)的符号。我们就将它称为“扫描方格”，符号被称为“扫描符号”。这样可以用机器来做计算，当符号被写下。会形成数列或是数字，数列与数字都是十进制的可以计算的。其余的记录全都用来记忆。而正是这些记录我们才认为计算是可信任的。这就是作者的关于书的计算的论点，下节会有关“machine机器”“纸带”和“扫描的”含义与理解。定义，解说自动机器如果这台机器的每个动作都完全由配置决定，我们就将这个机器叫做“自动机器”（或a—机器）。因为一些原因我们会使用部分动作由配置决定的机器（选择机器或c—机器）。当这样一台机器，任意的外部操作都会影响它的运行，没有外部操作它也根本无法运行。这篇论文只研究自动机器。计算机如果一台自动的机器包括两种符号，第一种（也叫数字）只包括0和1，其余的叫符号或第二种符号，那么这台机器就可称为计算机。符号打印的子数列称为“机器计算的数列”。二——十进制的数称为“机器计算的数”。纸带的符号和m—配置被称为完全配置。机器上合纸带上的改变叫做机器的一个步骤。循环和不循环的机器如果一台机器从来不写下多于有限个第一类数（0和1），那么它就叫做可循环的机器，否则就叫做不可循环的机器。计算数列与数如果一个数列可以被不可循环的机器运算，那么它就是可计算的。计算机的例子如果一个数列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记在一起。微型桌面几乎所有的机器都在用对应的进程，而且，一些机器用了许多链接。这些工程包括复制符号数列，比较两个数列，擦除已给形式的所有符号，等等。这样我们可以考虑用m-配置用于基于缩写有关的桌面。这些都是“变量”的自然意义。通过吧希腊文转化为德文，我们就获得了m-配置。我们可以用基干桌面造出微型桌面。基干桌面应该与微型桌面一样：它们不是必须的。我们可以说这个机器会有m-配置q和所有可得到的m-配置，会成为一个可以把c转化成p(c)的m-配置代替。这样就会得到qYp(q),p(p(q)),p(p(p(q)))。如果我们用q来代替C，用r代替B，用x代替I