Hiểu lầm kiểu zombie trong khoa học máy tính lý thuyết

Hiểu lầm kiểu zombie trong khoa học máy tính lý thuyết

Mở đầu

• Trong giáo trình "Introduction to the Theory of Computation" của Michael Sipser có một bài tập hoàn hảo
• Bài tập: "Khi hàm f:{0,1}*→{0,1} trả về 1 hoặc 0 tùy theo việc Chúa có tồn tại hay không, thì f có tính được không?"
• Đáp án: "Có, f là hàm tính được" (vì hàm hằng là hàm tính được)

Khái niệm về tính tính được

• Tính tính được được áp dụng cho hàm hoặc dãy vô hạn
• Không áp dụng cho một câu hỏi có/không riêng lẻ hay một số nguyên riêng lẻ
• Độ khó của việc viết chương trình không liên quan đến tính tính được

Bài toán P so với NP

• Bài toán P so với NP là một câu hỏi có/không riêng lẻ
• Tính NP-khó được áp dụng cho hàm hoặc ngôn ngữ
• Bài toán P so với NP không thể là không tính được hoặc NP-khó

Hàm Busy Beaver

• Hàm Busy Beaver là không tính được
• Các số nguyên riêng lẻ như BB(6) thì tính được
• Toàn bộ hàm BB là không tính được

Hiểu lầm kiểu zombie trong khoa học máy tính lý thuyết

• Áp dụng sai các khái niệm vốn dành cho dãy vô hạn và hàm vào các số nguyên riêng lẻ và các bài toán mở
• Nhầm lẫn giữa tính không tính được của bài toán dừng và tính bất toàn Gödel

Câu hỏi dành cho độc giả

• Tác giả đặt câu hỏi cho độc giả về cách có thể ngăn chặn hiểu lầm kiểu zombie này

Tóm tắt của GN⁺

• Bài viết này bàn về những hiểu lầm thường gặp trong khoa học máy tính lý thuyết
• Tính tính được được áp dụng cho hàm hoặc dãy vô hạn, chứ không áp dụng cho số nguyên riêng lẻ hay câu hỏi có/không
• Bài toán P so với NP là một câu hỏi riêng lẻ, không liên quan đến khái niệm NP-khó
• Hàm Busy Beaver là không tính được, nhưng các giá trị riêng lẻ thì tính được
• Bài viết sẽ giúp hiểu rõ hơn các khái niệm cơ bản của khoa học máy tính lý thuyết

[GN⁺]

Ý kiến trên Hacker News

• Việc có tồn tại thuật toán tính độ phức tạp Kolmogorov hay không liên quan đến tính vô hạn

  • Không tồn tại thuật toán tính độ phức tạp Kolmogorov cho các chuỗi có độ dài tùy ý
  • Nhưng có tồn tại thuật toán tính độ phức tạp Kolmogorov cho các chuỗi có độ dài nhỏ hơn n
  • Điều này khả thi bằng cách tạo một bảng tra cứu khổng lồ cho mọi chuỗi có thể có
  • Các bài toán hữu hạn luôn có thể được giải bằng chương trình, nhưng bài toán vô hạn thì không phải vậy

• Ý kiến cho rằng toán học kiến tạo phù hợp với trực giác của con người hơn

  • Vẫn chưa có bằng chứng rằng tồn tại một chương trình cho bài toán P=NP
  • Mark Braverman đã chứng minh mọi tập Julia (bậc hai) đều tính được, nhưng không tính được một cách đồng nhất
  • Trong toán học kiến tạo, mặt phẳng phức được chia thành nhiều vùng và chứng minh rằng tập Julia trong mỗi vùng là compact

• Lý do tính không quyết định được của bài toán dừng khó hiểu

  • Một trong hai chương trình "return true" và "return false" luôn đưa ra đáp án đúng
  • Khả năng quyết định chỉ trở thành không thể quyết định khi mở rộng ra vô hạn tổ hợp máy/đầu vào

• Biểu đạt các bài toán cần đến modal logic

  • Câu hỏi "f có tính được không?" là một câu hỏi sai về mặt modal
  • Câu hỏi "f có thể tính được không?" chính xác hơn
  • Điều này tương tự các chỉ thị compiler hoặc pragma

• Cách biểu diễn gây nhầm lẫn của hàm f

  • Hàm f không phân nhánh theo giá trị của "God exists"
  • Dù f là 0 hay 1 thì vẫn tính được
  • Sự nhầm lẫn phát sinh từ việc đẩy biến tự do vào điều kiện phân nhánh

• Sự khác biệt về ý nghĩa của tính quyết định được, tính tính được và sự tồn tại

  • Ý nghĩa khác nhau giữa ngữ cảnh học thuật và ngữ cảnh đời thường
  • Các số rất lớn tồn tại và tính được về mặt học thuật, nhưng trên thực tế không thể chứa trong vũ trụ

• Vấn đề của các câu hỏi liên quan đến "God exists"

  • Không rõ "God exists" là đúng hay sai
  • Đây là vấn đề phát sinh khi trộn ngôn ngữ tự nhiên với toán học

• Lý do khoa học máy tính lý thuyết và lý thuyết độ phức tạp khó với sinh viên cử nhân CS

  • Các thuật ngữ như NP-hard bị thay thế bằng các phép ví von và hình dung đại chúng

• Phàn nàn về cách blog nhấn mạnh văn bản

  • Màu nền của đoạn văn bản được chọn không thay đổi nên thiếu trực quan

• Đề xuất thay "God exists" bằng một mệnh đề toán học khác

  • Cần định nghĩa rõ "God exists" là đúng hay sai