Chung qui chỉ tại Cantor[note]
Note này tóm tắt lại loạt bài viết cùng tên của thầy Ngô Quang Hưng
Động lực: bài toán P chọi NP (bài toán xác định xem 1 vấn đề có thể có thuật giải trong thời gian đa thức hay không) -> từ đó đưa đến lý thuyết tính toán và sự phức tạp trong ngành máy tính:
In P or not in P, that is the question!
Hành trình tìm lời giải thích đưa ta đến với Cantor, Russell, Hilbert, Godel, Church, Turing, Cook/Levin, Karp- Cantor đưa ra lý thuyết tập hợp (th và lực lượng của th)-> lung lay nền tảng toán học, với câu hỏi về lực lượng của các tập vô hạn.
Tóm tắt của “tóm tắt” :)
- Cantor đưa ra lý thuyết tập hợp (th và lực lượng của th)-> lung lay nền tảng toán học, với câu hỏi về lực lượng của các tập vô hạn.
- Cantor ko tìm ra được |R|. Từ lý thuyết của ông nảy sinh nhiều nghịch lý: nl Russell (eg: tập tất cả các tập hợp, self-reference)… khiến cho nền toán học lung lay về nền tảng Logic -> tranh luận.
- Giải pháp:
- Trường phái logic - logicism(Principia Mathematica - Whitehead, Russell),
- Trường phái trực quan - intuitionism (là hệ thống triết học của Brouwer
- Trường phái hình thức - formalism: Hilbert, nhằm tiên đề hóa các nhánh toán học rồi chứng minh ko có nghịch lý -> ảnh hưởng rất lớn đến Toán học hiện nay.
- 1900 Hilbert đề nghị 23 bài toán làm kim chỉ nam cho nghiên cứu toán học của thế kỷ 20.
- Những năm đầu tk 20 Hilbert dành rất nhiều thời gian hoàn thiện chương trình của mình, rất nhiều nhà Toán học lừng danh khác cũng góp sức vào đó (Ackermann, Neumann…). Nhưng Godel với 3 định lý về sự toàn vẹn lừng danh đã “phá tan tành” chương trình của Hilbert (1931). Đại ý 3 định lý ấy cho ta biết rằng: Không thể có một hệ tiên đề hoàn thiện (không mâu thuẩn với bất kỳ mệnh đề nào được phát biểu trên đó) ie: cho dù hệ tiên đề có tốt đến đâu thì cũng luôn tồn tại 1 mệnh đề độc lập (không thể xác định được tính đúng sai) (eg: tiên đề V trong hệ tiên đề Euclide)
- Trong 20 bài toán của Hilbert, bài toán thứ 10 (về bản chất: “các hàm ntn có thể tính toán được”) có vai trò cực kỳ quan trọng hình thành khái niệm giải thuật và lý thuyết tính toán -> phép tính lambda(Church) tương đương với các hàm đệ quy (Herbrand-Godel)
- “Church tin rằng các hàm tính toán được đều là các hàm đệ qui.
- “Một giải thuật thật ra cũng là một hàm số (hay ánh xạ)”
- “cái gì tính được bằng một giải thuật thì tính được bằng giải tích lambda”
- Để chứng minh điều trên, Church và Turing độc lập tạo ra 2 pp khác nhau.
- Turing nghĩ ra máy Turing: mô hình máy hiểu khái niệm thuật toán, có thể bắt chước quá trình tính toán 1 cách cơ học của con người; nhờ các cách thiết kế #, máy Turing tính được rất nhiều hàm khác nhau; nhưng khả năng của máy Turing vẫn bị chặng bởi 1 bài toán dừng. Từ đó suy ra, khả năng của máy tính là có giới hạn.
- Cần nghiên cứu kỹ hơn: thực chất giới hạn ấy đến đâu (bởi vũ trụ cũng có giới hạn). Những năm 60, người ta bắt đầu quan tâm đến những bài toán mà thuật toán chạy chúng cần rất nhiều thời gian. Từ đó, bắt đầu định nghĩa lớp P - lớp các bài toán có thể giải trong thời gian đa thức.
- Lớp các bài toán “dễ” P được định nghĩa chính xác qua mô hình Toán học - máy Turing. Ngoài máy Turing xác định thông thường (giải được các bài toán P) còn có máy Turing bất định dùng để giải các bài toán NP. Vấn đề đặt ra, hai dạng máy này có mạnh bằng nhau ko? hay P=NP???
- Lớp những bài toán NP - đầy đủ chứa những bài toán NP đặc biệt, mà ngoài chúng ra, những bài toán NP còn lại có thể giản lược lại thành các bài toán P. Người ta đã tìm ra có khoảng hơn 23 bài toán NP trong tự nhiên.
- Việc tìm ra lời giải cho bài toán P=NP? rất quan trọng,liên quan đến nhiều ứng dụng NP trong thực tế (ví dụ: mã hóa Public key, khi tin rằng NP!= P), hay mở ra nhiều ngành nghiên cứu khoa học khác: thiết kế lại mô hình máy tính (ex: máy tính lượng tử), hay các hướng đi tìm lời giải khác: tìm cách hiệu quả nhất, tìm giá trị xấp xỉ trong thời gian đa thức, dùng giải thuật ngẫu nhiên hóa…
Nhiều cánh cửa mới đã mở ra, trong đó người đã mở 1 trong những cánh cửa quan trọng nhất đó chính là Cantor! (tới đây, mình nhớ đến định lý Ferma)
Sách nên đọc:
- Sách giải thuật: CRLS, computational
- Proofs from the book: Quyển sách về các chứng minh của thượng đế
- Các trường phái logic
- Diagonal Argument: Lý luận đường chéo đã dùng để chứng minh |S|<|2^S|
- P vs NP problem,máy Turing
