圖靈機的變體與邱奇-圖靈論題

原地不動移動(stay-put move)

基本圖靈機的讀寫頭閒不住:每一步它都必須向左或向右挪一格,即使那邊根本沒它要做的事。有時這很惱人,你會希望讀寫頭寫個符號後就待在原地,或許是為了下一步再讀同一格。原地不動移動(stay-put move)是一個賦予你這項能力的小變體:一個第三種讀寫頭方向,常寫作 S,意思是「這一步讀寫頭不要移動」。

具體而言,在基本模型中,轉移函數以 {L, R}(左或右)中的方向移動讀寫頭。原地不動機允許 {L, R, S},其中在 S 移動時,讀寫頭寫下新符號並改變狀態,但停在同一格。這純粹是給機器設計者的方便,他現在可以把「更新這格並重新考量它」想成單獨一步,而不必設計出「先右後左」的舞步。

重點、也是它屬於穩健性故事的原因,在於原地不動絲毫不增添能力。任何 S 步都能被普通機器以兩步模擬:向右(什麼有用的事都不做),再向左回到原格。所以原地不動圖靈機識別的語言與基本模型完全相同,至多慢一個常數倍。它是「一個看似順手的功能完全不改變可計算語言類別」最乾淨的示例之一,正是圖靈機變體那整個寓意的縮影。

假設一台機器想把當前格覆寫成 X,然後在下一個狀態立刻再讀一次 X。有原地不動移動時這是一步:δ(q, a) = (q', X, S)。沒有它時,同樣的效果要兩步:寫 X 並向右移,再向左移回來,中間什麼都沒改。

S = 不動;單一 S 步在基本機器上不過是「先右後左」,因此並未增添能力。

原地不動移動是「對可計算性純屬表面裝飾」之變體的教科書範例:它對被識別的類別毫無改變,只替設計者省下一步。

又称
stationary moveno-move optionstay optionS move不動移動