半無限帶圖靈機

帶半無限帶的圖靈機有一端，但沒有另一端。該端用結束標記限制。

它是一個雙軌帶：

• 上軌 - 它表示初始磁頭位置右邊的單元格。

• 下軌 - 它表示初始磁頭位置左邊的單元格，順序相反。

無限長的輸入字串最初寫在磁帶上的連續磁帶單元格中。

機器從初始狀態q₀開始，磁頭從左端的“End”標記開始掃描。在每一步中，它讀取磁頭下磁帶上的符號。它在該磁帶單元格上寫入一個新符號，然後它將磁頭向左或向右移動一個磁帶單元格。轉移函式確定要採取的操作。

它有兩個特殊狀態，稱為接受狀態和拒絕狀態。如果在任何時候它進入接受狀態，則接受輸入；如果它進入拒絕狀態，則圖靈機拒絕輸入。在某些情況下，對於某些特定的輸入符號，它會無限期地執行而不會被接受或拒絕。

注意 - 帶半無限帶的圖靈機等效於標準圖靈機。