Máy điều chỉnh không xác định
Trong Máy điều chỉnh không xác định, đối với mọi trạng thái và biểu tượng, có một nhóm hành động mà TM có thể thực hiện. Vì vậy, ở đây các chuyển đổi không mang tính xác định. Tính toán của Máy điều chỉnh không xác định là một cây cấu hình có thể đạt được từ cấu hình bắt đầu.
Đầu vào được chấp nhận nếu có ít nhất một nút của cây là cấu hình chấp nhận, nếu không thì không được chấp nhận. Nếu tất cả các nhánh của cây tính toán dừng lại trên tất cả các đầu vào, Máy điều chỉnh không xác định được gọi làDecider và nếu đối với một số đầu vào, tất cả các nhánh đều bị từ chối thì đầu vào cũng bị từ chối.
Máy Turing không xác định có thể được định nghĩa chính thức là bộ 6 bộ (Q, X, ∑, δ, q 0 , B, F) trong đó -
Q là một tập hợp hữu hạn các trạng thái
X là bảng chữ cái băng
∑ là bảng chữ cái đầu vào
δ là một hàm chuyển tiếp;
δ: Q × X → P (Q × X × {Left_shift, Right_shift}).
q0 là trạng thái ban đầu
B là biểu tượng trống
F là tập hợp các trạng thái cuối cùng