- Một bài toán quyết định P được cho là bán quyết định (tức là có một bán thuật toán) nếu ngôn ngữ L của tất cả các trường hợp có đối với P là r.e. - (Bài toán tương đương cho DFA) Cho hai DFA, chúng có chấp nhận cùng một ngôn ngữ không? Bằng chứng: Nhớ lại lập luận của Cantor từ Bài giảng đầu tiên.
Khi một vấn đề được cho là bán giải quyết được?
Các vấn đề Bán quyết định là những vấn đề đối với mà máy Turing dừng ở đầu vào được nó chấp nhận nhưng nó có thể dừng hoặc lặp mãi mãi trên đầu vào bị Máy Turing từ chối. Các vấn đề như vậy được gọi là các vấn đề có thể nhận dạng Turing.
Vấn đề quyết định một phần là gì?
Định nghĩa: Một có ngôn ngữ liên kếtlà ngôn ngữ liệt kê đệ quy. Tương tự, tồn tại một thuật toán tạm dừng và xuất ra 1 cho mọi trường hợp có câu trả lời "có", nhưng đối với các trường hợp có câu trả lời "không" được phép không dừng hoặc dừng và xuất ra 0.
Vấn đề tạm dừng có quyết định một phần không?
Alan Turing đã chứng minh vào năm 1936 rằng một thuật toán chung chạy trên máy Turing giải quyết vấn đề tạm dừng cho tất cả các cặp đầu vào chương trình có thể nhất thiết không thể tồn tại. Do đó, vấn đề dừng là không thể quyết định đối với máy Turing.
Tại sao vấn đề tạm dừng lại mang tính quyết định?
Một ngôn ngữ được cho là Bán quyết định nếu tồn tại một máy Turing tạm dừng nếu một từ thuộc ngôn ngữ(CÓ trường hợp) và có thể từ chối hoặc chuyển sang trạng thái vô hạn lặp lại nếu từ không thuộc ngôn ngữ (KHÔNG viết hoa chữ thường).
