Để chỉ ra rằng một ngôn ngữ có thể phân biệt được, chúng ta cần để tạo một máy Turing sẽ dừng trên bất kỳ chuỗi nhập nào từ bảng chữ cáicủa ngôn ngữ đó. Vì M là một dfa nên chúng ta đã có Máy Turing và chỉ cần hiển thị rằng dfa dừng ở mọi đầu vào.
Làm thế nào để bạn tính toán khả năng quyết định?
Một ngôn ngữ là có thể quyết định được nếu và chỉ khi nó và phần bổ sung của nó có thể nhận biết được. Bằng chứng. Nếu một ngôn ngữ có thể giải mã, thì phần bổ sung của nó có thể giải mã được (bằng cách đóng trong phần bổ sung).
Làm thế nào để bạn chứng minh Độ phân giải Turing?
Chứng minh rằng ngôn ngữ mà nó nhận dạng bằng với ngôn ngữ đã cho và thuật toán tạm dừng trên tất cả các đầu vào. Để chứng minh rằng một ngôn ngữ nhất định là có thể nhận dạng Turing: Xây dựng một thuật toán chấp nhận chính xác những chuỗi có trong ngôn ngữ Nó phải từ chối hoặc lặp lại trên bất kỳ chuỗi nào không phải bằng ngôn ngữ.
Làm thế nào để bạn biết liệu một ngôn ngữ có thể nhận dạng được hay không?
Ngôn ngữ L có thể nhận dạng được nếu và chỉ khi tồn tại một trình xác minh cho L, trong đó trình xác minh là một máy Turing dừng trên tất cả các đầu vào và cho tất cả w∈Σ ∗, w∈L↔∃c∈Σ ∗. V chấp nhận ⟨w, c⟩.
Làm thế nào để bạn cho thấy một vấn đề là không thể quyết định?
Vấn đề Tổng thể là Không thể quyết định
Vấn đề tạm dừngcó thể được sử dụng để chỉ ra rằng các vấn đề khác là không thể quyết định được. Bài toán tổng: Một hàm (hoặc chương trình) F được cho là tổng nếu F (x) được xác định với mọi x (hoặc tương tự, nếu F (x) dừng lại với mọi x). Việc xác định xem hàm F có là tổng hay không là không thể quyết định.
