Máy điều chỉnh băng bán vô hạn
Một Máy Turing có băng bán vô hạn có đầu bên trái nhưng không có đầu bên phải. Đầu bên trái được giới hạn bằng một điểm đánh dấu kết thúc.
Nó là một cuộn băng hai đoạn -
Upper track - Nó đại diện cho các ô ở bên phải của vị trí đầu ban đầu.
Lower track - Nó đại diện cho các ô bên trái vị trí đầu ban đầu theo thứ tự ngược lại.
Chuỗi đầu vào có độ dài vô hạn ban đầu được viết trên băng trong các ô băng liền nhau.
Máy bắt đầu từ trạng thái ban đầu q0và phần đầu quét từ điểm đánh dấu cuối bên trái 'End'. Trong mỗi bước, nó đọc ký hiệu trên băng dưới đầu của nó. Nó viết một ký hiệu mới trên ô băng đó và sau đó nó di chuyển đầu sang trái hoặc phải một ô băng. Một chức năng chuyển tiếp xác định các hành động được thực hiện.
Nó có hai trạng thái đặc biệt được gọi là accept state và reject state. Nếu tại bất kỳ thời điểm nào nó chuyển sang trạng thái được chấp nhận, đầu vào được chấp nhận và nếu nó đi vào trạng thái từ chối, đầu vào sẽ bị TM từ chối. Trong một số trường hợp, nó tiếp tục chạy vô hạn mà không được chấp nhận hoặc bị từ chối đối với một số ký hiệu đầu vào nhất định.
Note - Máy Turing có băng bán vô hạn tương đương với máy Turing tiêu chuẩn.