Theory of computation là gì?

Trong khoa học máy tính (computer science) và toán học (mathemati), lý thuyết tính toán (theory of computation) là nhánh đề cập đến những vấn đề nào có thể được giải quyết trên một mô hình tính toán, sử dụng một thuật toán (algorithm), mức độ hiệu quả của chúng có thể được giải quyết hoặc ở mức độ nào (ví dụ: các giải pháp gần đúng so với các giải pháp chính xác ). Lĩnh vực này được chia thành ba nhánh chính: lý thuyết automata (automata theory) và ngôn ngữ hình thức (formal language) ,lý thuyết về sự khả tính (computability theory) và lý thuyết độ phức tạp tính toán (computational complexity theory), được liên kết với nhau bằng câu hỏi: "Các khả năng và hạn chế cơ bản của máy tính là gì?".