杂谈235 图灵机和判定问题

邸继征

杂谈235 图灵机和判定问题

老邸

塔斯基的真之定义理论，消除了如说谎者悖论出现的可能性，它提供的T - 语句和T - 约定使得哥德尔定理的证明不必再回避使用真概念，哥德尔第一不完全性定理，就是由此直接推导出来的。

自然界的本质，以不可撼动的力量渗透到各个方面，这不，随着计算机的发明与发展，哥德尔与塔斯基探讨的同一种事物以可判定性问题的面貌出现了，结果自然也一样：人类到哪都有解决不了的问题。

一、图灵机的定义与作用

图灵机（Turing machine）是英国数学家阿兰·图灵（Alan Turing）于1936年设计的一种抽象机器，用于定义和模拟计算（computing）。它虽然构造简单，但却极其强大，能模拟现代计算机的所有计算行为，堪称计算的终极机器。图灵机的出现为计算理论奠定了基础，对计算机科学、逻辑学、数学和人工智能等领域产生了深远影响。

‌图灵机是一种抽象的数学模型，本质是描述计算过程的数学构造，包含无限长纸带、读写头、状态规则等抽象组件，实际制造不可行，关键限制在于‌无限纸带‌和‌理想化操作‌，现实中无法满足无限存储或绝对精确的控制。

简言之，图灵机是无实物的想象计算机，用于研究计算机原理时推演和模拟用。

下面介绍图灵机的工作原理。

为了告诉机器也就是图灵机干什么，需要编辑语句，于是需要写语句使用的符号。我们知道语言不同，使用符号不同，比如在英文环境下，符号是52个大小写英文字母和若干别的符号，在汉语环境下，是3500多个常用汉字和别的符号。所编辑的向机器发指令的语句，是符号的排列，如，十六除以二，是5个汉字的一种排列，这排列形成一个人和机器都懂的语句。

把编辑好的语句输入机器，机器内部有程序，能做许多事，例如可以判断这是不是一个正常的中文语句。对十六除以二，机器判断它是一个正常的指令，执行后输出计算结果：八。如果输入机器的是“以除二六十”，机器经判断，感觉不成正常语句，输出结果：拒绝。

所述机器即图灵机并没有造出来，那么上面的操作怎么进行呢？

答案是，人自己摆弄推演。心里认为机器已经有了，自己编出语句，按逻辑关系推导，这一步干什么，下一步怎么走，结果是什么。我们设计真实的机器时，不就是这样反复推演然后做出样品实际试验的吗？现在做样品这一步省掉了，不受物质条件限制了，思维可以更加活跃了，这是图灵机的极大优势。

二、判定问题相关概念与结果

1. 图灵可识别与图灵可判定

图灵机的识别对象是语言。看了前面的文字，容易理解下面的介绍。

图灵机特定语言包括图灵可识别语言（Turing machine recognizable language）和图灵可判定语言（Turing machine decidable language）。一台图灵机在读取一个语句后，可能进入三种状态：接受、拒绝、循环。接受的意思，是机器一定给出处理结果，然后停机；拒绝的意思，是问题本身无厘头，实际上为不可判定语句，比如输入的语句乱七八糟不像样，或者机器自己没能力处理，拒绝后也会停机；循环的意思，机器不停机，一直运行。

从上一节的叙述可以想象到，在图灵机上可以进行计算机的设计，可以发现所用语言方面的许多事，如怎么选符号，怎么编辑，包括怎么造算法，写程序等等。

2. 可判定性问题以及结论与意义

可做的事情很多，本文不谈，只谈图灵机的判定问题。

可判定性问题为：是否存在一种方法，能够在有限步骤内判断任意图灵机对于某个输入是否会停止？

这句话信息量很大。一种方法，具有万能性质，方法的面前是任意图灵机，方法要工作的对象，是一个语句，一段程序，在这句话或程序还没有接触图灵机之前，这方法就能判断出它的下场，是使机器出结果或拒绝从而完成运转，还是没完没了地工作下去？

这样万能的方法有吗？这个问题就是可判定性问题。

答案已经知道了：没有这样的方法！

这就是说，甭管人有多厉害，计算机有多强大，都有无法判定的语句，无法解决的问题。是不是出现了哥德尔面临的同类问题？

既然答案有了，遇到难以解决的问题，就认为是不能解决的问题躲开好了，行吗？不！不能动不动就以存在人类不能解决的问题为借口躲避困难，探索困难问题只是困难还是不能解决，以及相关因素，会源源不断产生好结果，如探索使机器能停机的问题，对研究可以揭示计算机能力的局限性，为后来的计算复杂性和不可判定性理论奠定了基础，也为我们理解计算机和算法的能力设定了框架。