定理：令X代表判定圖靈機(jī)工作帶上一段長度為L的固定區(qū)域，其上的讀寫頭若在X內(nèi)逗留時間超過M·s^L，則兩者必居其一：

（1）圖靈機(jī)將永不停機(jī)。

（2）X是有冗余的，將X的一部分刪除不會影響到圖靈機(jī)的判定。

M代表讀寫頭內(nèi)部狀態(tài)數(shù)，s代表工作帶符號數(shù)（含空白）。圖靈機(jī)的判定結(jié)果指讀寫頭停止在接受態(tài)還是拒絕態(tài)，故上述圖靈機(jī)的輸出只是一個0-1變量。

輸出包含多位二進(jìn)制數(shù)的一般情形可以看作是多次判定結(jié)果的組合。

從永不停的圖靈機(jī)沒法定義判定結(jié)果來看，（1）甚至可以看作（2）的特例，即：X不產(chǎn)生有意義輸出，整個都是可刪除的。

證明：長度為L的區(qū)域只有s^L個狀態(tài)，連同讀寫頭在內(nèi)總狀態(tài)數(shù)只有M·s^L個，故讀寫頭若在M·s^L步后仍不離開X，則X與讀寫頭的狀態(tài)必與先前重復(fù)。

1，如果讀寫頭的位置也和先前重復(fù)，那么，讀寫頭的后續(xù)行為是被狀態(tài)和位置完全決定的，讀寫頭將重復(fù)執(zhí)行該狀態(tài)復(fù)現(xiàn)間的所有步驟，無限循環(huán)這一周期。歸于結(jié)論（1）。

2，如果讀寫頭的位置和先前不重復(fù)，記先前的舊位置為i，新位置為j。不失一般性，不妨設(shè)j在i右方，從i到j(luò)前一位的工作帶區(qū)域記作X’。在圖靈機(jī)后續(xù)的運(yùn)行中：

①如果讀寫頭返回到X’內(nèi)。因?yàn)閄的狀態(tài)已經(jīng)被窮盡，X’作為其子區(qū)域狀態(tài)也已被窮盡，讀寫頭的狀態(tài)亦然。所以讀寫頭只要一進(jìn)入X’，就一定會陷入位置和狀態(tài)都重復(fù)的狀況，歸于結(jié)論（1）。

②如果讀寫頭不曾返回到X’內(nèi)。顯然X’的存在已經(jīng)完全不影響讀寫頭到達(dá)j以后的一切計(jì)算了。倒回去想，其實(shí)X’的存在也不影響之前的一切計(jì)算，因?yàn)樽x寫頭在穿過X’的過程中所做的一切改動都必須在抵達(dá)j前全部抵消掉，否則前后圖靈機(jī)的狀態(tài)是不會相同的，這與狀態(tài)必然重復(fù)矛盾。即：X’給圖靈機(jī)帶來的都是無用功。

將X’從X中剪除掉，直接讓讀寫頭走到j(luò)，圖靈機(jī)的運(yùn)行結(jié)果不會有變。這就歸于結(jié)論（2）。

推論1：排除永不停機(jī)的情況，占用運(yùn)行時間t>M·s^L的數(shù)據(jù)X至少可以被壓縮（t-M·s^L）的長度。

推論2：若數(shù)據(jù)X占用了運(yùn)行時間t>(L-1)+M·s^L，則必定永不停機(jī)。

我們現(xiàn)在可以說：占用判定時間太長的數(shù)據(jù)一定包含著冗余。

算法信息論中更常用的模型是輸出帶（只能寫入，單向移動）和工作帶（讀寫皆可，雙向移動）獨(dú)立分開的圖靈機(jī)，有效符號為0和1。輸入可以看作是工作帶初始包含的數(shù)據(jù)。

不難看出，最終停機(jī)時輸出帶上的每一位數(shù)都可以看作是單純記錄一次判定結(jié)果（寫下1對應(yīng)接受態(tài)，0對應(yīng)拒絕態(tài)）。故前述定理及推論仍然適用。