Làm thế nào là một cách mà người ta không nên xem phi quyết định?
Một máy Turing xác định là máy Turing cơ bản nhất, trong đó sử dụng một tập hợp cố định các quy tắc để xác định hành động trong tương lai của nó. Một máy Turing xác suất là một máy Turing xác định với một nguồn cung cấp thêm các bit ngẫu nhiên. Khả năng đưa ra quyết định xác suất thường giúp các thuật toán giải quyết vấn đề hiệu quả hơn. Các thuật toán sử dụng các bit ngẫu nhiên được gọi là thuật toán ngẫu nhiên. Một máy Turing không xác định là một máy Turing xác định với một tính năng bổ sung của phi xác định, cho phép một máy Turing có nhiều hành động trong tương lai có thể từ một trạng thái nhất định. Một cách để xem phi xác định là máy Turing nhánh thành nhiều đường dẫn tính toán có thể ở mỗi bước, và nếu nó giải quyết vấn đề trong bất kỳ của các nhánh, nó được cho là đã giải quyết vấn đề. Rõ ràng, mô hình này không có nghĩa là một mô hình vật lý có thể thực hiện được, nó chỉ là một máy trừu tượng lý thuyết thú vị mà làm phát sinh các lớp phức tạp đặc biệt thú vị. Ví dụ, xem thuật toán không xác định.