Điều gì phục vụ như là cơ sở của cả hai máy Turing xác suất và không xác định Dựa trên câu hỏi trước, hãy viết một ngữ cảnh chứa câu trả lời. Nó có thể là 1 - 20 câu. Nội dung
Máy Turing quyết định là máy Turing cơ bản nhất, sử dụng một bộ quy tắc cố định để xác định các 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áy Turing không quyết định là một máy Turing quyết định với một tính năng bổ sung của không quyết định, cho phép máy Turing có nhiều hành động tương lai có thể từ một trạng thái nhất định. Một cách để xem không xác định là máy Turing phân nhánh thành nhiều con đường tính toán có thể ở mỗi bước, và nếu nó giải quyết vấn đề trong bất kỳ nhánh nào trong số này, 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 có thể thực hiện được về mặt vật lý, nó chỉ là một máy trừu tượng lý thuyết thú vị tạo ra các lớp phức tạp đặc biệt thú vị. Đối với các ví dụ, xem thuật toán không xác định.