Các Mô hình Tính toán
Nhiều khuôn khổ hình thức định nghĩa thế nào là tính toán, từ việc viết lại hàm của phép tính lambda đến các mạch Boolean và hệ thống lượng tử, và việc so sánh sức mạnh của chúng cho thấy mô hình nào tương đương và mô hình nào thực sự khác biệt.
Definition
Một mô hình tính toán là một khuôn khổ trừu tượng chính xác quy định các phép toán được phép và cách một phép tính diễn ra; các mô hình khác nhau có thể tính toán cùng một lớp hàm nhưng khác nhau về tính ngắn gọn, tính song song hoặc các tài nguyên mà chúng làm rõ.
Scope
Lĩnh vực này bao gồm phép tính lambda và các mô hình hàm, các hàm đệ quy và máy đăng ký, các mạch Boolean và độ phức tạp mạch, và tính toán lượng tử, kiểm tra cách mỗi mô hình thể hiện các thuật toán, cách sức mạnh tính toán của chúng liên quan thông qua luận đề Church–Turing, và cách hiệu quả của chúng có thể phân kỳ.
Sub-topics
Core questions
- Có những cách khác nhau nào để hình thức hóa khái niệm tính toán?
- Những mô hình nào tương đương về các hàm mà chúng có thể tính toán, và tại sao?
- Các mô hình khác nhau như thế nào khi hiệu quả, tính song song hoặc khả năng hiện thực hóa vật lý trở nên quan trọng?
- Liệu một mô hình có động lực vật lý như tính toán lượng tử có thể vượt quá hiệu quả cổ điển không?
Key theories
- Sự tương đương theo luận đề Church–Turing
- Phép tính lambda, các hàm đệ quy, máy đăng ký và máy Turing đều tính toán chính xác cùng một lớp hàm, sự hội tụ này là nền tảng cho việc đồng nhất tính toán với khả năng tính toán Turing.
- Sự phân kỳ về hiệu quả
- Các mô hình đồng ý về khả năng tính toán có thể khác biệt rõ rệt về tài nguyên: các mạch làm lộ ra tính toán song song và không đồng nhất, và các mô hình lượng tử dường như mang lại sự tăng tốc, do đó việc lựa chọn mô hình rất quan trọng đối với độ phức tạp ngay cả khi nó không quan trọng đối với khả năng tính toán.
Clinical relevance
Các mô hình khác nhau làm sáng tỏ các khía cạnh khác nhau của tính toán thực tế: phép tính lambda là cơ sở lý thuyết của các ngôn ngữ lập trình hàm, các mạch mô hình hóa phần cứng và tính toán song song, máy đăng ký phản ánh các bộ xử lý thông thường, và các mô hình lượng tử hướng dẫn thiết kế phần cứng và thuật toán lượng tử mới nổi.
History
Vào những năm 1930, phép tính lambda của Church, các hàm đệ quy của Gödel và Kleene, và máy Turing đều được đề xuất và sau đó được chứng minh là tương đương. Các mô hình sau này đã bổ sung các chiều mới: độ phức tạp mạch đã hình thức hóa tính toán song song và phần cứng, và đề xuất của Feynman năm 1982 về mô phỏng lượng tử đã gieo mầm cho mô hình tính toán lượng tử.
Key figures
- Alonzo Church
- Alan Turing
- Stephen Kleene
- Richard Feynman
Related topics
Seminal works
- church1936
- sipser2013
- aroraBarak2009
Frequently asked questions
- Tại sao phải nghiên cứu nhiều mô hình nếu chúng tính toán cùng một hàm?
- Sự tương đương chỉ đúng với những gì có thể được tính toán về nguyên tắc. Các mô hình khác nhau giúp dễ dàng thể hiện hoặc phân tích những điều khác nhau: phép tính lambda làm rõ lập trình hàm, các mạch tiết lộ tính song song và chi phí phần cứng, và các mô hình lượng tử nắm bắt các hiện tượng vật lý, vì vậy mỗi mô hình là một lăng kính phù hợp cho các câu hỏi khác nhau.
- Tất cả các mô hình tính toán có tương đương không?
- Tất cả các mô hình cổ điển hợp lý đều tính toán cùng một lớp hàm, hỗ trợ luận đề Church–Turing. Nhưng chúng có thể khác biệt rất lớn về hiệu quả, và các mô hình khai thác các tài nguyên khác nhau, chẳng hạn như chồng chập lượng tử, có thể giải quyết một số vấn đề nhanh hơn ngay cả khi tính toán cùng một hàm.