Bạn sẽ học được gì
- Xây dựng và chứng minh tính đúng đắn của ô-tô-mát hữu hạn (DFA/NFA) cho một ngôn ngữ chính quy cho trước
- Chuyển đổi qua lại giữa biểu thức chính quy, NFA và DFA; dùng bổ đề bơm để chứng minh một ngôn ngữ không chính quy
- Thiết kế văn phạm phi ngữ cảnh và ô-tô-mát đẩy xuống cho một ngôn ngữ lập trình đơn giản
- Giải thích luận đề Church-Turing và mô phỏng máy Turing cho các bài toán tính toán cơ bản
- Chứng minh một bài toán không khả quyết bằng quy dẫn từ Bài toán dừng
- Phân loại bài toán vào P, NP, PSPACE và chứng minh NP-đầy đủ bằng quy dẫn đa thức
Nên học trước
Giới thiệu
Lý thuyết tính toán trả lời ba câu hỏi lớn: một máy tính lý tưởng tính được gì (automata, văn phạm), giới hạn tuyệt đối của tính toán ở đâu (khả quyết/bất khả quyết), và trong giới hạn đó, bài toán nào thực tế giải nhanh được (độ phức tạp). Đây là môn trừu tượng nhất trong khoa học máy tính, nhưng mọi khái niệm đều có mô hình cụ thể để vẽ ra giấy.
Ba mô hình máy tính, từ yếu đến mạnh
Ô-tô-mát hữu hạn (bộ nhớ cố định) → ô-tô-mát đẩy xuống (thêm một ngăn xếp) → máy Turing (thêm băng đọc/ghi vô hạn). Mỗi mô hình mạnh hơn nhận diện được lớp ngôn ngữ lớn hơn: chính quy ⊂ phi ngữ cảnh ⊂ khả quyết đệ quy. Luôn tự hỏi: mô hình này không làm được gì — chính giới hạn đó (bổ đề bơm, tính không khả quyết) mới là nội dung sâu sắc nhất.
Từ "tính được" đến "tính nhanh"
Máy Turing xác định cái gì tính được; độ phức tạp thời gian hỏi tính nhanh cỡ nào. Kỹ thuật quy dẫn xuất hiện ở cả hai tầng: quy dẫn từ Bài toán dừng để chứng minh bất khả quyết, quy dẫn đa thức từ 3-SAT để chứng minh NP-đầy đủ. Nắm vững một kiểu quy dẫn sẽ giúp hiểu kiểu còn lại rất nhanh.
Học chủ động, đừng chỉ học định nghĩa
Với mỗi định lý, tự vẽ ví dụ nhỏ trước khi đọc chứng minh: một DFA 3 trạng thái, một máy Turing mô phỏng phép cộng. Các bài giảng và bộ đề MIT 18.404 đi kèm lộ trình này rất giàu ví dụ — nên làm bài tập ngay sau mỗi buổi thay vì dồn lại.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Vì sao chọn: Sách mở, miễn phí toàn văn (CC BY-NC-ND), trình bày lý thuyết tính toán theo hướng hiện đại và trực quan, có thêm chương về mật mã học và tính toán lượng tử. Chọn làm sách chính vì bám sát đúng lộ trình automata → khả quyết → độ phức tạp của môn học này và không tốn chi phí.
Nên đọc: Automata and Regular Expressions; Defining Computation; Equivalent Models of Computation; Universality and Uncomputability; NP, NP-Completeness and the Cook-Levin Theorem; Space Bounded Computation
Introduction to the Theory of Computation
Michael Sipser · 2013 · Bản thứ 3
Sách giáo khoa kinh điển nhất của môn; các bài giảng MIT 18.404J trong lộ trình này bám theo đúng cấu trúc chương của sách. Nên đọc song song để có thêm bài tập và cách trình bày chứng minh cô đọng, chuẩn mực; bản tiếng Anh, không có bản đọc miễn phí hợp pháp.
Nên đọc: Chương 1–2 (Automata và ngôn ngữ), Chương 3–6 (Lý thuyết khả quyết), Chương 7–9 (Lý thuyết độ phức tạp)
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Ô-tô-mát hữu hạn và ngôn ngữ chính quy
khoảng 6 giờHọc DFA, NFA, biểu thức chính quy và các phép chuyển đổi qua lại giữa chúng; dùng bổ đề bơm để chứng minh một ngôn ngữ không chính quy. Tự xây một DFA nhận diện chuỗi nhị phân chia hết cho 3, rồi chứng minh bằng bổ đề bơm rằng {0^n1^n} không chính quy.
- Đọc: Chương Functions with Infinite Domains, Automata, and Regular Expressions — Introduction to Theoretical Computer Science
- Đọc: Chương 1 Regular languages — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Introduction, Finite Automata, Regular Expressions (MIT 18.404J, Lecture 1)Video
Video: Nondeterminism, Closure Properties, Regex → Finite Automata (MIT 18.404J, Lecture 2)VideoÔ-tô-mát hữu hạn và biểu thức chính quyTài liệuKhông đơn định, tính đóng kín và tương đương NFA–DFATài liệuBổ đề bơm cho ngôn ngữ chính quyTài liệuBước 2: Văn phạm phi ngữ cảnh và ô-tô-mát đẩy xuống
khoảng 6 giờHọc văn phạm phi ngữ cảnh, ô-tô-mát đẩy xuống và bổ đề bơm cho ngôn ngữ phi ngữ cảnh. Viết văn phạm phi ngữ cảnh cho biểu thức số học có ngoặc và chuyển nó thành một ô-tô-mát đẩy xuống.
- Đọc: Chương 2 Context-free languages — Introduction to the Theory of Computation
Video: Regular Pumping Lemma, FA → Regex, CFGs (MIT 18.404J, Lecture 3)Video
Video: Pushdown Automata, CFG ↔ PDA (MIT 18.404J, Lecture 4)Video
Video: CF Pumping Lemma, Turing Machines (MIT 18.404J, Lecture 5)VideoVăn phạm phi ngữ cảnh và Ô-tô-mát đẩy xuốngTài liệuBổ đề bơm phi ngữ cảnh và Máy TuringTài liệuBước 3: Máy Turing và luận đề Church-Turing
khoảng 6 giờĐịnh nghĩa máy Turing, các biến thể tương đương (nhiều băng, không đơn định) và luận đề Church-Turing. Mô phỏng tay một máy Turing đơn giản thực hiện phép cộng nhị phân trên băng.
- Đọc: Chương Defining Computation và Equivalent Models of Computation — Introduction to Theoretical Computer Science
- Đọc: Chương 3 The Church-Turing thesis — Introduction to the Theory of Computation
Bước 4: Tính khả quyết và quy dẫn
khoảng 7 giờHọc các bài toán khả quyết cho automata/văn phạm, Bài toán dừng và kỹ thuật quy dẫn để chứng minh bất khả quyết. Chứng minh bài toán 'một chương trình có bao giờ in ra chuỗi rỗng không' là không khả quyết bằng quy dẫn từ Bài toán dừng.
- Đọc: Chương Universality and Uncomputability — Introduction to Theoretical Computer Science
- Đọc: Chương 4 Decidability, Chương 5 Reducibility — Introduction to the Theory of Computation
Bước 5: Độ phức tạp thời gian: P, NP và NP-đầy đủ
khoảng 8 giờHọc lớp P, NP, định nghĩa NP-đầy đủ và Định lý Cook-Levin. Tự quy dẫn đa thức từ 3-SAT sang một bài toán đồ thị quen thuộc (như Independent Set) để chứng minh nó NP-đầy đủ.
- Đọc: Chương NP, NP Completeness, and the Cook-Levin Theorem — Introduction to Theoretical Computer Science
- Đọc: Chương 7 Time complexity — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Time Complexity (MIT 18.404J, Lecture 12)Video
Video: P and NP, SAT, Poly-Time Reducibility (MIT 18.404J, Lecture 14)Video
Video: NP-Completeness (MIT 18.404J, Lecture 15)Video
Video: Cook-Levin Theorem (MIT 18.404J, Lecture 16)VideoĐộ phức tạp thời gian: lớp P và NPTài liệuNP-đầy đủTài liệuĐịnh lý Cook-LevinTài liệuBước 6: Độ phức tạp không gian và các lớp nâng cao
khoảng 7 giờHọc PSPACE, Định lý Savitch, các lớp L/NL và các chủ đề nâng cao (định lý phân cấp, tính toán xác suất). Chọn một bài toán trò chơi hai người (như Generalized Geography) và chứng minh nó thuộc PSPACE.
- Đọc: Chương Space Bounded Computation — Introduction to Theoretical Computer Science
- Đọc: Chương 8 Space complexity, Chương 9 Intractability — Introduction to the Theory of Computation
Khái niệm chính
- Ô-tô-mát hữu hạn (DFA/NFA)
- Mô hình tính toán với số trạng thái hữu hạn, không có bộ nhớ ngoài; nhận diện đúng lớp ngôn ngữ chính quy.
- Bổ đề bơm (Pumping lemma)
- Công cụ chứng minh một ngôn ngữ không thuộc một lớp (chính quy hoặc phi ngữ cảnh) bằng cách chỉ ra chuỗi đủ dài luôn 'bơm' được mà vẫn phải thuộc ngôn ngữ, dẫn đến mâu thuẫn.
- Văn phạm phi ngữ cảnh & Ô-tô-mát đẩy xuống
- Văn phạm sinh ra cấu trúc lồng nhau (ngoặc, cú pháp lập trình); ô-tô-mát đẩy xuống là automaton tương đương, thêm một ngăn xếp vào DFA.
- Máy Turing & Luận đề Church–Turing
- Mô hình tính toán tổng quát nhất được biết; luận đề Church-Turing cho rằng mọi khái niệm 'thuật toán' hợp lý đều tương đương về sức mạnh với máy Turing.
- Tính khả quyết & Bài toán dừng
- Một bài toán khả quyết nếu có thuật toán luôn dừng và trả lời đúng/sai; Bài toán dừng là ví dụ kinh điển không khả quyết, chứng minh bằng đường chéo hóa.
- Quy dẫn (Reducibility)
- Chuyển một bài toán A về bài toán B đã biết tính chất; nếu B khả quyết và A quy dẫn được về B thì A cũng khả quyết — dùng theo chiều ngược để chứng minh bất khả quyết hoặc NP-khó.
- Lớp P, NP và NP-đầy đủ
- P là các bài toán giải được trong thời gian đa thức; NP là các bài toán mà lời giải có thể kiểm tra trong thời gian đa thức; NP-đầy đủ là các bài toán khó nhất trong NP.
Học xong để làm gì
- Trình biên dịch và bộ phân tích cú pháp: DFA cho từ vựng (lexer), văn phạm phi ngữ cảnh cho cú pháp (parser)
- Biểu thức chính quy (regex) dùng trong tìm kiếm văn bản, xác thực dữ liệu, xử lý log
- Kiểm chứng phần mềm và phần cứng: mô hình hóa hệ thống bằng automaton để chứng minh tính chất an toàn
- Mật mã học: độ an toàn của nhiều hệ mật mã dựa trên giả định P ≠ NP, tức không có thuật toán đa thức phá được
- Biết khi nào nên dừng tìm thuật toán tối ưu và chuyển sang heuristic — nhận diện bài toán NP-đầy đủ giúp tiết kiệm thời gian nghiên cứu
Câu hỏi thường gặp
Môn này có ứng dụng thực tế không hay chỉ là lý thuyết suông?
Regex, trình biên dịch, kiểm chứng phần mềm và cả việc biết khi nào nên ngừng tìm thuật toán tối ưu (vì bài toán NP-đầy đủ) đều dùng trực tiếp các khái niệm ở đây.
Sao phải học máy Turing khi không ai lập trình bằng nó?
Máy Turing không phải để lập trình — nó là công cụ toán học để chứng minh giới hạn của tính toán, tương tự dùng số thực trừu tượng để chứng minh định lý giải tích.
Làm sao để thành thạo các chứng minh bằng quy dẫn?
Làm nhiều bài tập quy dẫn theo mẫu có sẵn trước (ví dụ từ Bài toán dừng), nhận ra khuôn mẫu chung, rồi mới thử quy dẫn một bài toán mới hoàn toàn.
Cần thuộc lòng các chứng minh trong sách không?
Không cần thuộc lòng; quan trọng hơn là hiểu ý tưởng cốt lõi (đường chéo hóa, mô phỏng, đối số đếm) vì các bài tập mới thường tái dùng đúng những ý tưởng này.







