Sự khác biệt giữa Turing-Decidable và Co-Turing-Decidable

Question

Tôi thực sự đấu tranh với sự hiểu biết về sự khác biệt giữa hai điều này. Từ sách giáo khoa của tôi, về cơ bản, nó mô tả sự khác biệt bằng cách nói rằng

một ngôn ngữ được đồng hóa để nhận ra nếu nó bổ sung cho ngôn ngữ có thể nhận dạng được.

Tôi đoán phần của định nghĩa này tôi không hiểu là: ý nghĩa của nó là gì khi nó là một bổ sung cho một ngôn ngữ có thể nhận dạng được?

Bạn xác định chính xác xem đó có phải là bổ sung cho một ngôn ngữ khác không?

Answer 1

(Lưu ý - thuật ngữ "Turing decidable" và "co-Turing decidable" là giống nhau. Tuy nhiên, "Turing-recognizable" và "co-Turing-recognizable" không giống nhau, và điều này là Lý do cho việc này là nếu một ngôn ngữ là decidable, sau đó bổ sung của nó phải được decidable là tốt. Điều tương tự cũng không đúng với các ngôn ngữ dễ nhận biết.)

Trực giác, một ngôn ngữ là Turing-nhận ra nếu có một số chương trình máy tính, được đưa ra một chuỗi trong ngôn ngữ, có thể xác nhận rằng chuỗi thực sự là trong ngôn ngữ. Chương trình này có thể lặp vô hạn nếu chuỗi không phải là ngôn ngữ, nhưng nó được đảm bảo để luôn luôn chấp nhận nếu bạn cho nó một chuỗi trong ngôn ngữ.

Trong khi đúng là một ngôn ngữ có thể nhận dạng đồng bộ nếu đó là bổ sung cho ngôn ngữ có thể nhận dạng được, định nghĩa này không làm sáng tỏ những gì đang diễn ra. Trực giác, nếu một ngôn ngữ là đồng-Turing-nhận ra, nó có nghĩa là có một chương trình máy tính, với một chuỗi không phải là trong ngôn ngữ, cuối cùng sẽ xác nhận rằng chuỗi không phải là ngôn ngữ. Nó có thể lặp vô hạn nếu chuỗi thực sự nằm trong ngôn ngữ. Lý do cho điều này là đơn giản - nếu một số chuỗi w không được chứa trong một ngôn ngữ co-Turing-dễ nhận biết, thì chuỗi w đó phải được chứa trong phần bổ sung của ngôn ngữ co-Turing-recognizable, mà (theo định nghĩa) phải có thể nhận dạng được. Vì w nằm trong phần bổ sung Turing-recognizable, phải có một số chương trình có thể xác nhận rằng w thực sự là phần bổ sung. Do đó, chương trình này có thể xác nhận rằng w không có trong ngôn ngữ gốc có thể nhận dạng được.

Tóm lại, Turing-recognizability có nghĩa là có một chương trình có thể xác nhận rằng chuỗi w bằng ngôn ngữ và khả năng nhận dạng đồng nghĩa là có một chương trình có thể xác nhận rằng chuỗi w là không bằng ngôn ngữ.

Hy vọng điều này sẽ hữu ích!

Answer 2

Một ngôn ngữ được nhận dạng iff có một máy Turing sẽ dừng và chỉ chấp nhận các chuỗi trong ngôn ngữ đó và cho các chuỗi không có trong ngôn ngữ, TM hoặc từ chối, hoặc không dừng lại ở tất cả. Lưu ý: không có yêu cầu rằng Máy Turing nên tạm dừng cho các chuỗi không có trong ngôn ngữ.

Một ngôn ngữ là Decableable iff có một máy Turing sẽ chấp nhận các chuỗi bằng ngôn ngữ và từ chối các chuỗi không có trong ngôn ngữ.