Lý thuyết tính toán
Lý thuyết tính toán nghiên cứu những vấn đề nào về nguyên tắc có thể được giải quyết bằng thuật toán và phân loại những vấn đề không thể giải quyết được theo mức độ khó của chúng.
Definition
Lý thuyết tính toán, còn được gọi là lý thuyết đệ quy, là một nhánh của logic toán học làm rõ khái niệm về một hàm có thể tính toán hiệu quả, nghiên cứu các tập hợp và hàm mà thuật toán có thể và không thể tính toán, và đo lường độ khó tương đối của các vấn đề không thể giải quyết được.
Scope
Lĩnh vực này bao gồm các mô hình tính toán hình thức và luận đề Church-Turing, các tập hợp có thể tính toán được và có thể liệt kê được bằng tính toán, các vấn đề không thể quyết định được như vấn đề dừng, các khả năng rút gọn và bậc Turing dùng để đo lường khả năng không giải được tương đối, và hệ thống phân cấp số học phân tầng khả năng định nghĩa theo độ phức tạp của lượng từ.
Sub-topics
Core questions
- Ý nghĩa của việc một hàm hoặc tập hợp có thể tính toán được là gì?
- Những vấn đề tự nhiên nào không thể quyết định được bằng thuật toán?
- Làm thế nào để so sánh và xếp hạng độ khó của các vấn đề không thể giải quyết được?
- Độ phức tạp logic tương ứng với các cấp độ tính toán như thế nào?
Key theories
- Luận đề Church-Turing
- Khái niệm trực quan về khả năng tính toán hiệu quả trùng khớp với khả năng tính toán của máy Turing, tương đương với các hàm đệ quy và các hàm có thể định nghĩa bằng lambda, từ đó cố định một định nghĩa toán học vững chắc về thuật toán.
- Tính không giải được của vấn đề dừng
- Không có thuật toán nào có thể quyết định cho mọi chương trình và đầu vào liệu chương trình đó có dừng hay không, đưa ra ví dụ đầu tiên và điển hình về một vấn đề không thể quyết định được.
- Các bậc Turing
- Khả năng rút gọn Turing xếp hạng các tập hợp theo khả năng tính toán tương đối, và các bậc được tạo ra tạo thành một thứ tự riêng phần phong phú mà cấu trúc của nó, bao gồm sự tồn tại của các bậc trung gian, là một đối tượng nghiên cứu trung tâm.
Clinical relevance
Lý thuyết tính toán xác định giới hạn tuyệt đối của khả năng giải quyết bằng thuật toán, làm nền tảng cho khoa học máy tính lý thuyết và cung cấp các kết quả về tính không thể quyết định, chẳng hạn như tính không giải được của vấn đề dừng và vấn đề từ, những vấn đề này lặp lại trong toán học và cung cấp thông tin cho lý thuyết độ phức tạp tính toán.
History
Lý thuyết tính toán ra đời vào những năm 1930 khi Church, Turing, Kleene và Post độc lập hình thức hóa khái niệm về một quy trình hiệu quả thông qua phép tính lambda, máy Turing, các hàm đệ quy và các hệ thống tổ hợp, tất cả đều được chứng minh là tương đương. Post và Kleene đã phát triển lý thuyết về các bậc và hệ thống phân cấp số học, và phương pháp ưu tiên được giới thiệu vào những năm 1950 đã thúc đẩy nghiên cứu cấu trúc sâu sắc về các bậc có thể liệt kê được bằng tính toán.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- Lý thuyết tính toán có giống với lý thuyết độ phức tạp không?
- Không. Lý thuyết tính toán hỏi liệu một vấn đề có thể được giải quyết bằng bất kỳ thuật toán nào hay không, bỏ qua các tài nguyên, trong khi lý thuyết độ phức tạp hỏi một vấn đề có thể giải quyết được cần bao nhiêu thời gian hoặc bộ nhớ. Lý thuyết tính toán vạch ra ranh giới giữa có thể giải quyết được và không thể giải quyết được; độ phức tạp phân loại phía có thể giải quyết được.
- Tại sao luận đề Church-Turing không phải là một định lý?
- Nó đánh đồng một khái niệm không chính thức, khả năng tính toán hiệu quả, với một khái niệm toán học chính xác, vì vậy nó không thể được chứng minh một cách hình thức. Sự chấp nhận của nó dựa trên sự hội tụ của nhiều hình thức hóa độc lập vào cùng một lớp hàm, đây là bằng chứng mạnh mẽ hơn là một chứng minh.