定理：令X代表判定图灵机工作带上一段长度为L的固定区域，其上的读写头若在X内逗留时间超过M·s^L，则两者必居其一：
（1）图灵机将永不停机。
（2）X是有冗余的，将X的一部分删除不会影响到图灵机的判定。
M代表读写头内部状态数，s代表工作带符号数（含空白）。图灵机的判定结果指读写头停止在接受态还是拒绝态，故上述图灵机的输出只是一个0-1变量。
输出包含多位二进制数的一般情形可以看作是多次判定结果的组合。
从永不停的图灵机没法定义判定结果来看，（1）甚至可以看作（2）的特例，即：X不产生有意义输出，整个都是可删除的。
证明：长度为L的区域只有s^L个状态，连同读写头在内总状态数只有M·s^L个，故读写头若在M·s^L步后仍不离开X，则X与读写头的状态必与先前重复。
1，如果读写头的位置也和先前重复，那么，读写头的后续行为是被状态和位置完全决定的，读写头将重复执行该状态复现间的所有步骤，无限循环这一周期。归于结论（1）。
2，如果读写头的位置和先前不重复，记先前的旧位置为i，新位置为j。不失一般性，不妨设j在i右方，从i到j前一位的工作带区域记作X’。在图灵机后续的运行中：
①如果读写头返回到X’内。因为X的状态已经被穷尽，X’作为其子区域状态也已被穷尽，读写头的状态亦然。所以读写头只要一进入X’，就一定会陷入位置和状态都重复的状况，归于结论（1）。
②如果读写头不曾返回到X’内。显然X’的存在已经完全不影响读写头到达j以后的一切计算了。倒回去想，其实X’的存在也不影响之前的一切计算，因为读写头在穿过X’的过程中所做的一切改动都必须在抵达j前全部抵消掉，否则前后图灵机的状态是不会相同的，这与状态必然重复矛盾。即：X’给图灵机带来的都是无用功。
将X’从X中剪除掉，直接让读写头走到j，图灵机的运行结果不会有变。这就归于结论（2）。
推论1：排除永不停机的情况，占用运行时间t>M·s^L的数据X至少可以被压缩（t-M·s^L）的长度。
推论2：若数据X占用了运行时间t>(L-1)+M·s^L，则必定永不停机。
我们现在可以说：占用判定时间太长的数据一定包含着冗余。
算法信息论中更常用的模型是输出带（只能写入，单向移动）和工作带（读写皆可，双向移动）独立分开的图灵机，有效符号为0和1。输入可以看作是工作带初始包含的数据。
不难看出，最终停机时输出带上的每一位数都可以看作是单纯记录一次判定结果（写下1对应接受态，0对应拒绝态）。故前述定理及推论仍然适用。
网友评论