線性加速定理

在計算複雜性理論中，圖靈機的線性加速定理是指：給定任意實數 c > 0 ，如果有任意圖靈機在 f(n) 時間內可以解決一個問題 L 則一定存在另一個圖靈機可以在 cf(n) + n + 2 的時間內解決這個問題 L。

簡要證明

這裡提供一個對於 c = 1/2 時的簡要的證明思路。假設一個包含有 k 條帶和 s 個狀態的圖靈機 M 可以在 f(n) 的時間內解決這個問題，構造一個新的圖靈機 M' 包含 k³ 條帶，每一個符號表示一個 M 中連續的三個符號的一個區塊，即 M' 的帶上的符號是 M 上的符號的壓縮表示—— M' 的第 i 格上的符號表示 M 的第 2i-1 格、第 2i 格和第 2i+1 格的一個區塊上的符號（注意：這些區塊之間是交疊的）。在一個計算步驟中，M' 模擬 M 的計算步驟直到 M 的讀寫頭離開 M' 當前讀寫頭所表示的對應區塊到左側或右側的下一格（這一模擬可以在一步中完成，因為 M 在不離開 M' 中對應區塊或重複一個狀態的情況下最多有 3sk³ 種狀態）。在這一模擬過程中， M 有可能接受（解決此問題），對應的 M' 也會接受（解決此問題）；或者 M 會一直循環下去，對應的 M' 會什麼也不做（或也對應的一直循環下去）。

最後一點需要注意的地方是：由於區塊可以交疊，因此這些區塊可能會在交疊出包含不連續的字符。在這種情況下，最接近當前讀寫頭位置的區塊才是正確的。當發生從一個區塊到另一個區塊的轉換時，圖靈機的狀態被用來暫時記錄開始區塊的那些交疊的符號，直到其可以被複製到目的區塊的對應位置。

這一構造需要 M' 的每一步計算要對應 M 的至少兩步計算。因此 M' 在最初的花費線性步驟的將輸入帶轉換為壓縮表示的步驟之後，最多還需要不會超過 f(n)/2 步。

這一證明可以被很容易的推廣到所有的 c > 0 的情況，通過讓每個區塊使用更多相鄰的符號來實現。一種叫做「帶壓縮定理」的相似技術可以用來在圖靈機所需的空間上去掉常因數。