Semi-Infinite Tape Turing Machine
Maszyna Turinga z pół-nieskończoną taśmą ma lewy koniec, ale nie ma prawego końca. Lewy koniec jest ograniczony znacznikiem końca.
Jest to taśma dwuścieżkowa -
Upper track - Przedstawia komórki na prawo od początkowej pozycji głowy.
Lower track - Przedstawia komórki po lewej stronie początkowej pozycji głowy w odwrotnej kolejności.
Ciąg wejściowy o nieskończonej długości jest początkowo zapisywany na taśmie w ciągłych komórkach taśmy.
Maszyna startuje ze stanu początkowego q0a głowy skanuje od lewego znacznika końcowego „End”. Na każdym kroku odczytuje symbol na taśmie pod głową. Zapisuje nowy symbol na tej komórce taśmy, a następnie przesuwa głowę do lewej lub prawej jednej komórki taśmy. Funkcja przejścia określa działania, które należy podjąć.
Ma dwa specjalne stany zwane accept state i reject state. Jeśli w dowolnym momencie wejdzie w stan akceptacji, dane wejściowe zostaną zaakceptowane, a jeśli przejdą w stan odrzucenia, to dane wejściowe zostaną odrzucone przez TM. W niektórych przypadkach nadal działa w nieskończoność, bez akceptacji lub odrzucenia niektórych symboli wejściowych.
Note - Maszyny Turinga z pół-nieskończoną taśmą są odpowiednikiem standardowych maszyn Turinga.