Bỏ qua tới nội dung chính

Trước khi có lý thuyết tính toán

Lý thuyết tính toán: máy tính làm được gì — và không bao giờ làm được gì

Từ máy trạng thái hữu hạn tới máy Turing, từ biểu thức chính quy tới bài toán dừng: lý thuyết tính toán vẽ ra giới hạn của mọi máy tính.

Ban biên tập OpenER

Cập nhật 09/11/2026 · 16 phút đọc · CC BY 4.0

Mỗi năm máy tính lại nhanh hơn, bộ nhớ lớn hơn, trí tuệ nhân tạo làm được những việc mười năm trước ta tưởng không thể. Rất dễ nghĩ rằng chỉ cần đủ thời gian và đủ máy, máy tính sẽ giải được mọi bài toán.

Không phải vậy. Có những câu hỏi mà không một chương trình nào trả lời đúng được trong mọi trường hợp — không phải vì máy chưa đủ mạnh, mà vì điều đó không thể, giống như không thể vẽ một hình tam giác có bốn cạnh. Ví dụ đơn giản nhất: không thể viết một chương trình nhận vào một chương trình bất kỳ và luôn trả lời đúng "chương trình này có chạy mãi không dừng hay không". Điều này đã được chứng minh từ năm 1936 — trước khi chiếc máy tính điện tử đa năng đầu tiên ra đời.

Môn học vẽ ra những giới hạn đó là lý thuyết tính toán (theory of computation). Nó là phần trừu tượng nhất của khoa học máy tính, và cũng là phần lâu bền nhất: ngôn ngữ lập trình, phần cứng, framework sẽ thay đổi; những định lý trong môn này đúng mãi.

Trước khi có lý thuyết tính toán

Đầu thế kỷ XX, "máy tính" (computer) không phải là một cái máy, mà là một nghề. Người làm nghề này ngồi bên bàn với giấy, bút và bảng số, làm theo những quy tắc đã cho sẵn để tính bảng lượng giác, quỹ đạo thiên thể, đường bay của đạn pháo. Họ không cần hiểu bài toán; chỉ cần làm đúng từng bước.

Cũng thời đó, các nhà toán học mơ một giấc mơ lớn. Năm 1928, David Hilbert nêu ra bài toán quyết định (Entscheidungsproblem): liệu có một quy trình máy móc nào — làm theo từng bước như người làm nghề tính toán — nhận vào một mệnh đề toán học bất kỳ và luôn trả lời được nó đúng hay sai? Nếu có, toán học sẽ thành một việc tính toán thuần túy. Nhưng có một khó khăn: không ai định nghĩa chính xác "quy trình máy móc" là gì. Không có định nghĩa thì không thể chứng minh nó không tồn tại.

Câu trả lời đến từng bước:

  1. Gödel (1931) chứng minh các định lý bất toàn: trong mọi hệ toán học đủ mạnh, luôn có mệnh đề đúng mà hệ đó không chứng minh được. Giấc mơ của Hilbert bắt đầu rạn.
  2. Church và Turing (1936) — độc lập với nhau — lần đầu định nghĩa chính xác "tính toán được". Alonzo Church dùng phép tính lambda; Alan Turing, khi mới 24 tuổi, tưởng tượng một cỗ máy đơn giản mô phỏng đúng người làm nghề tính toán: một băng giấy dài vô hạn chia ô, một đầu đọc ghi, và một bảng quy tắc. Đó là máy Turing. Cả hai cùng chứng minh: bài toán quyết định của Hilbert không có lời giải.
  3. Thập niên 1940–1950: những máy tính thật ra đời, và lý thuyết đi tiếp theo hướng ngược lại — từ máy mạnh nhất xuống những máy đơn giản hơn. Warren McCulloch và Walter Pitts (1943), rồi Stephen Kleene (1956) mô tả máy trạng thái hữu hạn và biểu thức chính quy; Noam Chomsky (1956) phân loại các loại văn phạm — nền móng của mọi trình biên dịch về sau.
  4. Thập niên 1960–1970: câu hỏi chuyển từ "giải được không" sang "giải nhanh được không" — lý thuyết độ phức tạp tính toán, P và NP.

Lý thuyết đi trước máy móc là chuyện hiếm trong lịch sử kỹ thuật. Bài báo năm 1936 của Turing còn chứa một ý tưởng nữa: một máy Turing vạn năng (universal Turing machine) đọc mô tả của bất kỳ máy nào khác từ băng giấy rồi chạy theo nó. Đó chính là ý tưởng chương trình lưu trong bộ nhớ — thứ biến máy tính từ một cỗ máy làm một việc thành cỗ máy làm được mọi việc.

Đặt cạnh nhau:

Không có lý thuyết tính toán
Có lý thuyết tính toán
"Tính toán được" là gì
Một ý niệm mơ hồ
Định nghĩa chính xác: máy Turing (và mọi mô hình tương đương)
Gặp bài toán mãi không giải được
Không biết do mình kém, do máy yếu, hay do không thể
Chứng minh được khi nào là không thể
So sức mạnh hai ngôn ngữ lập trình
Tranh cãi cảm tính
Biết chắc: các ngôn ngữ đa năng mạnh như nhau
Viết trình biên dịch, công cụ tìm kiếm văn bản
Làm thủ công, dễ sai
Có công cụ sẵn: máy trạng thái, văn phạm, bộ sinh trình phân tích cú pháp
Bảo mật
Không biết dựa vào đâu
Dựa vào những bài toán được tin là khó

Thiếu lý thuyết tính toán vẫn khiến người ta mất công tới hôm nay. Những dự án hứa hẹn "công cụ phát hiện mọi lỗi trong mọi chương trình", "phần mềm diệt virus phát hiện được mọi virus, kể cả virus chưa xuất hiện" — đều đang hứa điều mà lý thuyết đã chứng minh là không làm được. Công cụ thật chỉ có thể gần đúng: bỏ sót một số lỗi, hoặc báo nhầm một số chỗ không phải lỗi. Biết điều đó giúp bạn chọn và dùng công cụ đúng cách, thay vì đi tìm một thứ không tồn tại.

Môn này trả lời câu hỏi gì

Môn Lý thuyết tính toán trả lời ba câu hỏi, từ dễ tới khó:

  1. Lý thuyết automat (automata theory): những cỗ máy đơn giản — có ít bộ nhớ hoặc bộ nhớ hạn chế — làm được những gì?
  2. Lý thuyết khả tính (computability theory): bài toán nào có thể giải bằng máy tính, với bất kỳ thời gian và bộ nhớ nào?
  3. Lý thuyết độ phức tạp (complexity theory): trong những bài toán giải được, bài toán nào giải được nhanh?

Vì sao cần học, khi môn này gần như không có code? Vì nó cho bạn biết ranh giới: khi nào nên tìm lời giải chính xác, khi nào phải chấp nhận lời giải gần đúng, và khi nào nên ngừng hẳn. Và vì những công cụ của nó — máy trạng thái, biểu thức chính quy, văn phạm — là thứ lập trình viên dùng mỗi tuần mà thường không biết tên.

Năm ý tưởng cốt lõi

1. Máy trạng thái hữu hạn và biểu thức chính quy

Một chiếc máy bán nước tự động không cần nhớ bạn đã bỏ vào những đồng nào, chỉ cần nhớ tổng hiện tại: 0, 5.000, 10.000, đủ tiền. Mỗi đồng xu đẩy nó từ trạng thái này sang trạng thái khác. Đó là một máy trạng thái hữu hạn (finite automaton): một tập hữu hạn trạng thái, và quy tắc chuyển trạng thái theo từng ký hiệu vào. Đèn giao thông, cửa xoay, giao thức mạng, nhân vật trong game — đều là máy trạng thái.

Kleene chứng minh rằng những gì máy trạng thái hữu hạn nhận biết được chính là những gì mô tả được bằng biểu thức chính quy (regular expression) — thứ bạn dùng mỗi khi kiểm tra định dạng dữ liệu. Ví dụ, kiểm tra một chuỗi có phải số di động Việt Nam 10 chữ số hay không:

python
import re

def la_so_di_dong(s):
    # bắt đầu bằng 0, chữ số thứ hai là 3, 5, 7, 8 hoặc 9, rồi đúng 8 chữ số nữa
    return re.fullmatch(r"0[35789]\d{8}", s) is not None

print(la_so_di_dong("0912345678"))   # True
print(la_so_di_dong("0123456789"))   # False

Đằng sau dòng re.fullmatch là một máy trạng thái được dựng từ biểu thức. Năm 1968, Ken Thompson — người về sau viết Unix — công bố cách biến biểu thức chính quy thành máy trạng thái chạy nhanh trên máy tính; ý tưởng đó còn sống trong công cụ grep và trong hầu hết trình soạn thảo ngày nay.

2. Thứ máy hữu hạn không làm được: văn phạm và cấu trúc lồng nhau

Hãy thử viết một biểu thức chính quy kiểm tra một chuỗi ngoặc có cân bằng hay không: (()()) đúng, (() sai. Bạn sẽ không làm được — và môn học chứng minh vì sao không ai làm được. Để biết ngoặc có cân bằng không, máy phải đếm số ngoặc đang mở, và con số đó có thể lớn tùy ý. Một máy chỉ có hữu hạn trạng thái thì chỉ "đếm" được tới một giới hạn nào đó. Công cụ chứng minh có tên bổ đề bơm (pumping lemma).

Để mô tả cấu trúc lồng nhau, ta cần một bậc cao hơn: văn phạm phi ngữ cảnh (context-free grammar), và loại máy tương ứng có thêm một ngăn xếp (stack). Chuỗi ngoặc cân bằng được mô tả bằng một quy tắc ngắn:

text
S → ( S ) S | rỗng

Đây chính là cách mọi trình biên dịch đọc code: một câu lệnh if chứa khối lệnh, khối lệnh chứa câu lệnh if khác, biểu thức chứa biểu thức con. Ngôn ngữ lập trình, JSON, HTML đều được định nghĩa bằng văn phạm. Đó cũng là lý do câu nói vui quen thuộc trong giới lập trình — "đừng phân tích HTML bằng biểu thức chính quy" — có cơ sở toán học thật.

Chomsky xếp các loại văn phạm thành một thang, gọi là phân cấp Chomsky: chính quy, phi ngữ cảnh, cảm ngữ cảnh, và không giới hạn — mỗi bậc cần một loại máy mạnh hơn bậc trước.

3. Máy Turing và luận đề Church–Turing

Ở đỉnh thang là máy Turing: một bảng quy tắc hữu hạn, cộng với một băng giấy đọc ghi được, dài bao nhiêu cũng được. Nghe đơn sơ tới mức buồn cười — nhưng mọi thứ chiếc laptop của bạn làm được, một máy Turing đều làm được (chậm hơn rất nhiều).

Điều kỳ lạ là mọi mô hình "hợp lý" người ta từng nghĩ ra — phép tính lambda của Church, máy Turing, máy có nhiều băng, máy có bộ nhớ truy cập ngẫu nhiên, mọi ngôn ngữ lập trình đa năng — hóa ra đều mạnh như nhau: cái này làm được gì thì cái kia cũng làm được. Nhận định rằng chúng nắm bắt đúng ý niệm "tính toán được bằng một quy trình máy móc" gọi là luận đề Church–Turing. Nó không phải một định lý (vì "quy trình máy móc" là ý niệm đời thường), nhưng chưa ai tìm được phản ví dụ.

Hệ quả thực tế: Python, C, JavaScript hay một ngôn ngữ bạn tự viết — nếu đủ mạnh để có vòng lặp không giới hạn và bộ nhớ không giới hạn — đều là Turing đầy đủ (Turing complete): giải được đúng cùng một tập bài toán. Chúng khác nhau ở tốc độ, độ tiện, độ an toàn, không ở sức mạnh. Thậm chí "Trò chơi cuộc sống" (Game of Life) của John Conway — chỉ là một lưới ô sáng tắt theo ba quy tắc đơn giản — cũng đã được chứng minh là Turing đầy đủ.

4. Bài toán dừng: giới hạn tuyệt đối

Giả sử ai đó đưa bạn một hàm thần kỳ dung(p, x): nhận vào mã nguồn của chương trình p và dữ liệu x, luôn trả lời đúng p chạy trên x có dừng hay không. Turing chỉ ra rằng hàm đó không thể tồn tại, bằng một lập luận ngắn tới bất ngờ. Viết thêm một chương trình nữa (đoạn code chỉ để minh họa lập luận — vì hàm dung không tồn tại, nó không chạy được):

python
def nghich(p):
    if dung(p, p):       # nếu p chạy trên chính mã của nó mà dừng...
        while True:      # ...thì chạy mãi
            pass
    else:
        return           # còn nếu p chạy mãi, thì dừng ngay

Bây giờ hỏi: nghich(nghich) có dừng không?

  • Nếu dung nói "có dừng", thì nghich đi vào vòng lặp vô hạn — tức là không dừng. Sai.
  • Nếu dung nói "không dừng", thì nghich trả về ngay — tức là có dừng. Lại sai.

Dù dung trả lời gì cũng sai. Vậy không thể có hàm dung đúng với mọi chương trình. Đây là bài toán dừng (halting problem), và kỹ thuật "cho chương trình tự chạy trên chính nó" gọi là phép chéo hóa (diagonalization) — cùng họ với lập luận của Cantor về các loại vô hạn và của Gödel về sự bất toàn.

Từ bài toán dừng suy ra cả một họ kết quả. Định lý Rice nói: mọi câu hỏi không tầm thường về hành vi của chương trình — có bao giờ chia cho không, có bao giờ gửi dữ liệu ra ngoài, có làm đúng đặc tả không — đều không quyết định được trong trường hợp tổng quát. Đó là nền tảng toán học của nhận xét ở trên: không thể có công cụ phát hiện mọi lỗi, hay phần mềm diệt mọi virus.

5. Độ phức tạp: giải được nhưng có nhanh không

Trong những bài toán giải được, lý thuyết độ phức tạp chia chúng theo tài nguyên cần dùng. Hai lớp nổi tiếng nhất:

  • P: giải được trong thời gian đa thức theo kích thước dữ liệu — tạm hiểu là "giải nhanh được". Sắp xếp, tìm đường ngắn nhất, nhân ma trận.
  • NP: kiểm tra được một lời giải trong thời gian đa thức. Cho một lịch thi, kiểm tra nó có trùng giờ không rất dễ; còn tìm ra một lịch không trùng thì có thể rất khó.

Câu hỏi P có bằng NP không — mọi bài toán dễ kiểm tra có đều dễ giải không — là câu hỏi mở lớn nhất của ngành, đã được nhắc trong bài Thiết kế và phân tích thuật toán. Môn Lý thuyết tính toán đi sâu vào công cụ chính để trả lời những câu hỏi như vậy: phép quy dẫn (reduction) — chứng minh "nếu giải được bài A thì giải được bài B", nhờ đó so độ khó giữa hai bài mà không cần giải bài nào. Cùng công cụ đó dùng cho cả bài toán dừng: muốn chứng minh một bài toán mới không quyết định được, ta quy dẫn bài toán dừng về nó.

Ngoài P và NP còn một vườn bách thú các lớp khác: bài toán giải được với ít bộ nhớ, bài toán giải nhanh nếu được tung đồng xu, bài toán giải nhanh bằng máy tính lượng tử. Mật mã hiện đại đứng trên đúng mảnh đất này: nó an toàn chỉ vì một số bài toán — như phân tích một số rất lớn ra thừa số nguyên tố — được tin là khó với máy tính thông thường.

Lý thuyết tính toán nằm ở đâu trong chồng tầng

Nếu bạn đã đọc Từ electron đến ứng dụng, máy tính là một chồng tầng trừu tượng, từ electron lên tới ứng dụng. Lý thuyết tính toán nằm dưới cả tầng thấp nhất — không phải dưới về vật lý, mà dưới về ý nghĩa. Nó định nghĩa chính "máy tính" là gì, độc lập với việc máy làm bằng bóng bán dẫn, bằng ánh sáng hay bằng qubit.

Đưa lên

định nghĩa thế nào là tính toán được, các mô hình máy (máy trạng thái, máy ngăn xếp, máy Turing), và bản đồ độ khó của bài toán.

Giấu đi

mọi chi tiết vật lý — mạch điện, tần số, bộ nhớ đệm — vì những thứ đó không đổi được ranh giới giữa "giải được" và "không giải được".

Học trước và học sau

· 7 môn

Toán rời rạc, logic và chứng minh

Mathematics for Computer Science

Học trước sẽ dễ hơn: chứng minh, quy nạp, tập hợp.

Xem chủ đề trên OpenER: Mathematics for Computer Science

Logic cho khoa học máy tính

Logic for Computer Science

Học trước sẽ dễ hơn.

Xem chủ đề trên OpenER: Logic for Computer Science

Thiết kế và phân tích thuật toán

Design and Analysis of Algorithms

Học trước, cho phần độ phức tạp.

Xem chủ đề trên OpenER: Design and Analysis of Algorithms

Ngôn ngữ lập trình và trình biên dịch

Programming Languages and Compilers

Học sau: automat, văn phạm, phân tích cú pháp.

Xem chủ đề trên OpenER: Programming Languages and Compilers

Mật mã học

Cryptography

Học sau, dùng lại môn này.

Xem chủ đề trên OpenER: Cryptography

Phương pháp hình thức

Formal Methods for Software Engineering

Học sau: kiểm chứng chương trình — và giới hạn của nó.

Xem chủ đề trên OpenER: Formal Methods for Software Engineering

Khoa học và công nghệ thông tin lượng tử

Quantum Information Science and Technology

Học sau: máy tính lượng tử làm nhanh được những gì.

Xem chủ đề trên OpenER: Quantum Information Science and Technology

Ứng dụng thật và nghề nghiệp

  • Trình biên dịch và công cụ ngôn ngữ: bộ phân tích từ vựng là máy trạng thái, bộ phân tích cú pháp là văn phạm; trình định dạng code, công cụ tô màu cú pháp, công cụ kiểm tra lỗi đều dựng trên đó.
  • Xử lý văn bản và dữ liệu: biểu thức chính quy trong tìm kiếm, kiểm tra dữ liệu nhập, trích xuất thông tin từ nhật ký hệ thống.
  • Bảo mật và phân tích chương trình: công cụ tìm lỗ hổng, phân tích tĩnh — biết giới hạn của chúng nhờ định lý Rice.
  • Kiểm chứng hình thức: chứng minh phần mềm và phần cứng quan trọng (chip, hệ thống máy bay, hợp đồng thông minh) làm đúng đặc tả.
  • Mật mã: thiết kế hệ thống an toàn dựa trên bài toán khó.
  • Nghiên cứu: độ phức tạp, tính toán lượng tử, nền tảng lý thuyết của học máy.

Học xong làm được gì, bắt đầu từ đâu

Sau môn này bạn có thể:

  • thiết kế máy trạng thái và biểu thức chính quy cho một bài toán nhận dạng, và biết khi nào chúng không đủ;
  • viết văn phạm cho một ngôn ngữ nhỏ — bước đầu để tự viết một trình thông dịch;
  • nhận ra một bài toán không quyết định được, và chứng minh điều đó bằng phép quy dẫn;
  • đọc các lập luận về P, NP và độ khó mà không thấy xa lạ;
  • giải thích cho người khác vì sao "công cụ tìm mọi lỗi" là lời hứa không thể giữ.

Nên biết trước: quen với chứng minh toán học — quy nạp, phản chứng, tập hợp và hàm. Đây là môn đọc và viết chứng minh nhiều hơn viết code. Chưa vững thì đi qua chủ đề Mathematics for Computer Science trước.

Bắt đầu trên OpenER: trang chủ đề Theory of Computation có các khóa học đã chọn lọc, và hướng dẫn học gợi ý thứ tự đi qua chúng. Lời khuyên cho môn này: tự vẽ máy. Mỗi khi gặp một automat hay một máy Turing, lấy giấy ra chạy tay nó trên vài chuỗi; và mỗi chứng minh, thử tự viết lại mà không nhìn sách. Môn này không vào đầu bằng cách đọc lướt.

Tài liệu tham khảo

  • Michael Sipser — Introduction to the Theory of Computation.
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman — Introduction to Automata Theory, Languages, and Computation.
  • MIT 18.404J / 6.1400J Theory of Computation — bài giảng của Michael Sipser trên MIT OpenCourseWare.
  • Stanford CS 103 Mathematical Foundations of Computing — nhập môn chứng minh, automat và khả tính.
  • Charles Petzold — The Annotated Turing: đọc bài báo năm 1936 của Turing từng dòng, có chú giải.

Bước tiếp theo trong hướng dẫn: Lý thuyết tính toán

Ban biên tập OpenER, “Lý thuyết tính toán: máy tính làm được gì — và không bao giờ làm được gì”, OpenER, 2026. Phát hành theo CC BY 4.0: được chia sẻ, chỉnh sửa, kể cả thương mại, miễn ghi công tác giả và dẫn link bài gốc.