Tất cả các ngôn ngữ đã biết mà máy Turing không thể chấp nhận là gì?

Question

Đối với example, ngôn ngữ của máy Turing không chấp nhận mã hóa riêng của chúng không thể được chấp nhận bởi bất kỳ máy Turing nào.

Answer 1

Có vô số ngôn ngữ mà không có TM nào có thể quyết định. Thật vậy, "hầu hết" ngôn ngữ là không thể xác định được; có rất nhiều ngôn ngữ có thể giải mã được, nhưng vô số ngôn ngữ (do đó, nhiều thứ không thể xác định được).

Định lý của Rice cho phép bạn tìm ra nhiều ví dụ về ngôn ngữ không thể đoán trước được. Xem trang Wikipedia: Rice's Theorem

Về cơ bản, nếu bạn có một bộ ngôn ngữ không tầm thường (nghĩa là có các TM nhận dạng ngôn ngữ trong tập hợp và TM nhận ra ngôn ngữ không có trong bộ), thì là không thể xác định được liệu một ngôn ngữ của TM tùy ý có ở S. Ví dụ, hãy S là tập hợp chứa ngôn ngữ trống. Sau đó, nó là không thể xác định để xác định xem một TM tùy ý chấp nhận ngôn ngữ trống rỗng, tức là, không có chuỗi. Hãy đến với bất kỳ bộ ngôn ngữ không tầm thường nào và bạn có một ngôn ngữ không thể đoán trước mới (tất cả các mã hóa của các TM nhận dạng ngôn ngữ trong tập hợp).