企业官网建设流程全解析

温州阀门网站建设,昆明网站建设论坛,室内设计公司取名,烟台网络推广什么是图灵停机问题概念#xff1a;图灵停机问题#xff08;Halting Problem#xff09;是否可判定#xff0c;形式化而言#xff1a;停机不停机对角线证明对角线#xff0c;实际上逻辑系统中的符号完备问题也是通过该法构造解答的由于所有的图灵机都可以由 序列编码图灵停机问题Halting Problem是否可判定形式化而言停机不停机对角线证明对角线实际上逻辑系统中的符号完备问题也是通过该法构造解答的由于所有的图灵机都可以由序列编码所以图灵机是可数的我们可以枚举出所有的图灵机。假设存在某个函数能判定任何图灵机对 任何输入是否停机那么我们可以构造一个图灵机使得显然这个图灵机和枚举的所有图灵机都不相同而且这个图灵机可以经由函数构造出来该函数本身也是一个图灵机。这与列举了所有的图灵机相悖所以我们可以得出不存在这样的即图灵停机问题不可判定。使用对角线对图灵机的证法说明了可数的无限中包含了不可数无限的性质即后者表现在前者中但是前者所在的系统无法表达这种性质即斯寇伦佯谬Skolems paradox。构造法证明思路与证明通常使用反证法与构造法。那么首先假设存在接下来构造矛盾问题是矛盾应当体现在何处它的根源是什么从而得出假设为错。考虑引入中间过程。一般而言应当体现出 递归 或者 否定 的性质才能体现出矛盾。然而若是一般的递归则由于永远需要一个输入。这显然会导致函数参数的不一致。譬如此处考虑停机不停机具体而言其中的停机可由直接返回表示不停机由死循环表示。那么如果使用来判断其是否停机则函数变成显然与题设不符虽然可以直观地将后二者压缩成一个参数但是这对内部的判断条件并不友好。所以此处的问题是如何防止参数长度的变化或者说如何消去参数呢答案是将参数实例化为已有的特征换句话说将图灵机本身作为参数因为它既是「机器」又是「语言」此处即为 自我递归 或者 自我指涉。那么显然地我们有停机不停机显然该图灵机矛盾故而证否。该证明中利用的矛盾是自我指涉该自我指涉的根源是图灵机的二义性即上文所提它既是「机器」又是「语言」。其体现在图灵机既作为「执行机构」又作为「输入内容」。构造法证明之我见除此之外我们还可以用假设做什么上文将参数固化此处直接获取参数。设while (i in I H(m, i) 1);return i; 用于获取使不停机的的输入。则显然可知要么要么。此法也可以避免参数长度不一致的问题。于是可以构建不停机停机可以看出判断中并没有出现的参数这给了我们操作的余地。若则说明不存在令其不停机的输入然而此处它却停机故而矛盾若则说明存在令其不停机的输入此处令其为输入即则此时它应该不停机然而根据定义它却停机故而矛盾。故而证否。该证明为本人在思考如何去除参数而保证参数长度一致性时想出既然通过传参的方式行不通那么就直接在内部生成也可以看出这种方法保证了参数的任意性。在构造的过程中发现该生成函数也是一个不知何时停机的图灵机那么可以基于假设构造矛盾基本思想仍然是自我指涉但是和上一证明存在本质的不同。此处矛盾的根源是纯粹语义上的循环递归性其体现在外部的输入和内部函数输入构造的对应性。其次需要说明的是的内部使用了本身这是否可以。当然可以因为里面的M是「语言」。