Máy tính thật sự giải được gì, và làm sao mình biết?

Có một câu hỏi cơ bản mà mình cứ trăn trở mãi: máy tính thật sự có thể giải quyết được những gì?

Không phải theo nghĩa phần cứng. Không phải "nó chạy nhanh cỡ nào" hay "cần bao nhiêu bộ nhớ." Mà là theo nghĩa sâu hơn — loại bài toán nào máy tính có thể giải được? Và nếu có hai bài toán, làm sao biết cái nào khó hơn?

Nghe như câu hỏi triết học, nhưng thật ra không phải. Có những câu trả lời mang tính hệ thống và chính xác tuyệt đối. Và bộ công cụ để tìm ra những câu trả lời đó gọi là lý thuyết tính toán (theory of computation).

Đây là bài đầu tiên trong một series mới — mình sẽ đi từ những cỗ máy đơn giản nhất cho đến những mô hình mạnh mẽ nhất, để xem ranh giới của tính toán thực sự nằm ở đâu. Series này đi theo cấu trúc của cuốn Introduction to the Theory of Computation của Sipser — cuốn sách giáo khoa chuẩn cho mảng này.

Mọi thứ bắt đầu từ một câu hỏi có-hoặc-không

Điều đầu tiên cần hiểu là toàn bộ lĩnh vực này đơn giản hoá mọi bài toán về một dạng duy nhất: bài toán quyết định (decision problem).

Bài toán quyết định là bất kỳ câu hỏi nào mà câu trả lời chỉ có có hoặc không. Vậy thôi. Nhị phân. Đúng hoặc sai. Một hoặc không.

Cách đặt vấn đề này không mới đâu. Năm 1928, David Hilbert và Wilhelm Ackermann đã đặt ra Entscheidungsproblem — dịch sát nghĩa là "bài toán quyết định" — hỏi rằng liệu có thuật toán nào đọc được một phát biểu toán học bất kỳ rồi trả lời có/không một cách máy móc hay không. Cả lĩnh vực này phát triển từ việc cố trả lời đúng câu hỏi đó.

Nghe có vẻ hạn chế, nhưng đây là điểm hay: hầu như bài toán nào cũng có thể chuyển thành bài toán quyết định.

• "Đường ngắn nhất từ A đến B là gì?" — đó là bài toán tối ưu.
• "Có tồn tại đường đi từ A đến B không?" — đó là bài toán quyết định.

Bài toán tối ưu hỏi đáp án là gì. Bài toán quyết định hỏi đáp án có tồn tại không. Và hoá ra, hiểu được phiên bản có/không cho bạn rất nhiều lợi thế để giải phiên bản khó hơn.

Không phải bài toán quyết định nào cũng khó như nhau

Thử nghĩ về bốn bài toán này:

1. Một file cụ thể có tồn tại trên máy bạn không?
2. Đoạn code này có compile được không?
3. Có lỗi runtime trong đoạn code này không?
4. Hệ thống của bạn có hoàn toàn không thể hack được không?

Bài đầu tiên? Tìm trong hệ thống file là xong. Bài thứ hai? Chạy compiler — nó hoặc thành công hoặc báo lỗi. Những thứ này có công cụ xử lý tốt rồi.

Nhưng chứng minh hệ thống hoàn toàn không thể bị hack? Bạn có thể test với các kiểu tấn công đã biết, nhưng làm sao đảm bảo không có kỹ thuật nào bạn chưa nghĩ tới? Cái đó khó ở một tầm khác — và như mình sẽ thấy trong series này, nó thật sự khó hơn, theo cách có thể chứng minh được. Nói cách khác, theo Định lý Rice (1953), ta không thể dùng một chương trình để tự động kiểm tra mọi đặc điểm quan trọng của một chương trình khác.

Video 30 phút kể lại cách Gödel và Turing đã chứng minh có những câu hỏi có/không không máy nào trả lời nổi.

Quan trọng là: "độ khó" không phải là chuyện hên xui hay chỉ là cảm giác. Có một hệ thống phân cấp cực kỳ chặt chẽ, và xây dựng hệ thống đó chính là mục tiêu của series này.

Trước khi đi vào các định nghĩa khô khan, thử kiểm tra trực giác của bạn xem sao. Hãy kéo năm bài toán dưới đây lên trục độ khó — bên trái là dễ nhất, bên phải là "bất khả thi" — rồi xem đáp án để thấy bản chất thực sự của chúng.

Mọi đầu vào đều chỉ là một chuỗi ký tự

Mô hình như sau. Với bất kỳ bài toán quyết định nào:

• Đầu vào là một chuỗi (string).
• Đầu ra là có hoặc không.

Thực tế thì đầu vào có thể là đồ thị, danh sách, số nguyên, hình ảnh — đủ loại. Nhưng tất cả đều có thể mã hoá thành một chuỗi ký tự. Trick này có từ lâu rồi: năm 1931, Gödel numbering đã chỉ ra rằng có thể biến bất kỳ phát biểu logic nào thành một con số duy nhất. Nên lý thuyết giả định việc mã hoá đã xong, và ta chỉ làm việc với chuỗi.

Chính sự đơn giản hóa này là "chìa khóa" giúp toàn bộ khung lý thuyết này trở nên mạch lạc và có thể xử lý được. Dù bài toán gốc phức tạp cỡ nào, ta luôn có thể rút gọn câu hỏi thành: "cho chuỗi này, có hay không?" Turing đã tận dụng triệt để cái "mẹo" này trong bài báo năm 1936 của ông — bài báo định nghĩa "máy tính" thật sự nghĩa là gì.

Các khối xây dựng: bảng chữ cái, chuỗi, và ngôn ngữ

Để làm việc với chuỗi một cách hình thức, ta cần vài định nghĩa.

Bảng chữ cái (alphabet, viết là Σ) là một tập hữu hạn, không rỗng các ký hiệu. Hiểu đơn giản là những ký tự bạn được phép dùng.

Chuỗi (string hay word) là một dãy các ký hiệu từ bảng chữ cái đó. Độ dài của chuỗi là số ký hiệu trong nó. Và có một chuỗi đặc biệt: chuỗi rỗng (empty string, viết là ε), có độ dài bằng không.

Ngôn ngữ (language) đơn giản là một tập hợp các chuỗi. Đó là thuật ngữ hình thức cho "một nhóm chuỗi có chung tính chất nào đó mà ta quan tâm."

Nên khi nói về bài toán quyết định, ta thật ra đang hỏi: "chuỗi đầu vào này có thuộc ngôn ngữ này không?"

Ý nghĩa của |x| thay đổi tùy theo kiểu dữ liệu

Lưu ý nhỏ: đừng để ký hiệu này làm bạn rối. Ký hiệu |x| có nghĩa khác nhau tuỳ kiểu dữ liệu của x:

Tất cả đều liên quan đến "kích thước" theo nghĩa nào đó, nhưng ý nghĩa chính xác phụ thuộc vào kiểu dữ liệu. Trong lĩnh vực này, ta chủ yếu dùng cho tập hợp (lực lượng) và chuỗi (độ dài).

Xây dựng ngôn ngữ bằng ba phép toán

Giờ ta đã có ngôn ngữ, ta cần cách kết hợp chúng. Có ba phép toán cơ bản: hợp (union), nối (concatenation), và Kleene star.

Phép hợp (Union)

Đúng như bạn nghĩ. Nếu R₁ và R₂ là hai ngôn ngữ, thì R₁ ∪ R₂ là ngôn ngữ chứa mọi chuỗi có trong một trong hai R₁ hoặc R₂.

Để ý ba xuất hiện ở cả hai tập, nhưng trong phép hợp ta chỉ liệt kê một lần. Tập hợp không có phần tử trùng — một phần tử hoặc thuộc tập hoặc không. Lực lượng ở đây là 5, không phải 6.

Phép nối (Concatenation)

Nếu R₁ và R₂ là ngôn ngữ, thì R₁ ∘ R₂ là ngôn ngữ gồm tất cả chuỗi tạo ra bằng cách lấy một chuỗi từ R₁ rồi dán một chuỗi từ R₂ vào cuối.

Điểm khác biệt giữa phép nối và tích Descartes: phép nối có thể tạo ra chuỗi trùng nhau. Nếu ab ∘ ε = ab và a ∘ b = ab, hai cách tạo ra cùng một chuỗi. Nhưng vì kết quả là tập hợp, ab chỉ xuất hiện một lần.

Ví dụ cụ thể. Cho R₁ = {ab, ba, a} và R₂ = {bb, b, ε}.

Ngôn ngữ kết quả là {abbb, abb, ab, babb, bab, ba, a} — bảy chuỗi phân biệt, không phải chín.

Phép nối cũng không có tính giao hoán. Đổi chỗ R₁ và R₂ cho ra ngôn ngữ khác vì thứ tự dán quan trọng.

Kleene star

Kleene star là phép toán trên một ngôn ngữ. R* nghĩa là: lấy mọi tổ hợp có thể của các phép nối chuỗi từ R, kể cả không nối gì cả.

Hai điều cần nhớ:

1. ε luôn nằm trong R.* Luôn luôn. Dù R là gì. Vì việc nối "không phần tử nào" theo định nghĩa sẽ trả về chuỗi rỗng.
2. R thường là vô hạn.* Bạn cứ nối thêm mãi, tạo ra chuỗi dài hơn nữa.

Chỉ có hai ngoại lệ — hai ngôn ngữ mà khi lấy Kleene star vẫn cho tập hữu hạn:

Tập rỗng star cho {ε}. Tập chỉ chứa chuỗi rỗng star cũng cho {ε}. Mọi ngôn ngữ khác đều tạo ra tập vô hạn khi lấy Kleene star.

Ví dụ nhanh. Nếu R = {a, bc, ε}, thì R* bao gồm:

• ε (không nối)
• a, bc (một phần tử)
• aa, abc, bca, bcbc, a, bc (hai phần tử nối — có trùng)
• aaa, aabc, abca, ... (ba phần tử nối)
• ... và tiếp tục mãi

Kết quả là ngôn ngữ vô hạn chứa mọi tổ hợp có thể của a và bc xếp cạnh nhau.

Hãy thử nghiệm trực tiếp với ba phép toán này. Nhập các ngôn ngữ hữu hạn bất kỳ (dùng ε cho chuỗi rỗng) và xem hợp, nối, Kleene star thay đổi ngay lập tức. Giới hạn độ dài là thứ duy nhất giữ cho Kleene star không chạy đến vô tận.

Tập rỗng và chuỗi rỗng là hai thứ hoàn toàn khác nhau

Nhiều người hay nhầm chỗ này, nên mình nói rõ luôn.

∅ là một cái hộp rỗng. ε là một từ có độ dài bằng không. Khác kiểu dữ liệu hoàn toàn, chỉ tình cờ đều liên quan đến "không có gì" thôi.

Biểu thức chính quy: cách mô tả ngôn ngữ

Mọi thứ ta đã xây — bảng chữ cái, chuỗi, ngôn ngữ, hợp, nối, Kleene star — kết hợp lại trong biểu thức chính quy (regular expression).

Biểu thức chính quy không phải là ngôn ngữ. Nó là mô tả của ngôn ngữ. Giống như "tất cả số chẵn" mô tả một tập hợp, biểu thức chính quy mô tả một tập hợp các chuỗi.

Các ký hiệu cơ bản

Với bảng chữ cái Σ = {0, 1}, các khối xây dựng của biểu thức chính quy là:

Mỗi ký hiệu cơ bản mô tả một ngôn ngữ có tối đa một chuỗi.

Các phép toán

Ta kết hợp các ký hiệu cơ bản bằng ba phép toán quen thuộc:

• Hợp (union, viết là ∪ hoặc |)
• Nối (concatenation, thường viết bằng cách đặt cạnh nhau)
• Kleene star (viết là *)

Và dùng ngoặc đơn để nhóm lại.

Thứ tự phép toán

Giống như nhân trước cộng trong số học, biểu thức chính quy có:

1. Kleene star trước (ưu tiên cao nhất)
2. Nối tiếp theo
3. Hợp cuối cùng (ưu tiên thấp nhất)

Nên ab* nghĩa là "a rồi theo sau bởi không hoặc nhiều b" — star chỉ áp dụng cho b, không phải cho ab.

Ký hiệu L(R)

Để phân biệt rõ giữa biểu thức chính quy R và ngôn ngữ mà nó mô tả, ta viết L(R) — "ngôn ngữ được mô tả bởi R."

R là mô tả. L(R) là tập hợp chuỗi thật sự.

Vài ví dụ

Thử với bảng chữ cái Σ = {a, b}.

Ví dụ 1: Ngôn ngữ {a, b, c}.

Biểu thức chính quy: a ∪ b ∪ c

Vì a tự nó nghĩa là {a}, và hợp gộp chúng lại.

Ví dụ 2: Ngôn ngữ {aⁿ : n ≥ 0} = {ε, a, aa, aaa, ...}

Biểu thức chính quy: a*

Kleene star cho mọi số lượng a có thể, kể cả không.

Ví dụ 3: Ngôn ngữ {aⁿ : n ≥ 1} = {a, aa, aaa, ...}

Biểu thức chính quy: a*a (hoặc tương đương aa*)

Lấy tất cả chuỗi a từ Kleene star rồi nối thêm một a, dịch mọi thứ lên một và loại bỏ ε.

Ta cũng có thể vẽ chính ngôn ngữ này dưới dạng automaton hữu hạn — đọc một chữ a để đến trạng thái chấp nhận, rồi cứ ở đó với mỗi chữ a tiếp theo:

Việc một biểu thức chính quy và một máy trạng thái mô tả cùng một ngôn ngữ chính là cây cầu nối qua bài tiếp theo trong series.

Ví dụ 4: Ngôn ngữ {a, ab, abb, abbb, ba, bab, babb, babbb}

Cái này phức tạp hơn. Phân tích:

Phần b ở cuối là {ε, b, bb, bbb}. Đó không phải b* (vì b* bao gồm cả bbbb, bbbbb, ...). Nên ta phải liệt kê: (ε ∪ b ∪ bb ∪ bbb).

Phần đầu {ε, ba} cho ta tiền tố ba tuỳ chọn.

Biểu thức chính quy đầy đủ: (ε ∪ ba) a (ε ∪ b ∪ bb ∪ bbb)

Điều mình thấy hay ở biểu thức chính quy: bản thân ký hiệu chỉ giới hạn trong ba phép toán. Không có phép trừ, không có giao. Vậy mà ba phép toán đó đủ để mô tả một lớp ngôn ngữ rộng đến bất ngờ.

Hướng đi tiếp theo của series

Series này sẽ đi qua ba loại mô hình tính toán:

1. Automaton hữu hạn (finite automata) — loại máy đơn giản nhất. Chúng đọc đầu vào từng ký tự một, không có bộ nhớ gì ngoài trạng thái hiện tại. Biểu thức chính quy mô tả đúng lớp ngôn ngữ mà những máy này nhận dạng được.

2. Automaton đẩy xuống (pushdown automata) — automaton hữu hạn cộng thêm stack. Bộ nhớ thêm đó cho phép xử lý lớp ngôn ngữ rộng hơn (ngôn ngữ phi ngữ cảnh), bao gồm những thứ như khớp ngoặc đơn và phân tích cú pháp ngôn ngữ lập trình.

3. Máy Turing — mô hình mạnh nhất. Chúng có bộ nhớ không giới hạn và có thể di chuyển cả hai hướng trên đầu vào. Đây là chỗ mọi thứ trở nên thật sự thú vị, vì ta sẽ phát hiện ra rằng ngay cả máy Turing cũng có giới hạn. Có những bài toán nó chứng minh được là không giải được.

Nửa sau của series sẽ tập trung vào việc đẩy máy Turing đến điểm giới hạn — tìm ra chính xác chỗ nào tính toán kết thúc. Lý do ta tin được giới hạn đó là luận đề Church-Turing: Alonzo Church và Alan Turing đã độc lập chứng minh rằng mọi định nghĩa hợp lý về khả năng "tính được" đều quy về cùng một lớp bài toán.

📺 Series bài giảng: MIT 18.404J — Theory of Computation, Sipser (Fall 2020) — khoá học miễn phí của MIT OCW do chính tác giả cuốn sách giáo khoa mà series này theo dạy.

Một vài điều mình rút ra được

• Mọi bài toán tính toán đều có thể chuyển thành bài toán quyết định — câu hỏi có/không về việc một chuỗi có thuộc ngôn ngữ hay không
• Không phải bài toán quyết định nào cũng khó như nhau, và lý thuyết cho ta cách so sánh mức độ khó một cách hình thức — không chỉ dựa vào cảm giác
• Bảng chữ cái, chuỗi và ngôn ngữ là những từ vựng cơ bản nhất — mọi thứ khác đều được phát triển dựa trên ba khái niệm này
• Hợp, nối, và Kleene star là ba phép toán duy nhất cần thiết để xây ngôn ngữ phức tạp từ những thứ đơn giản
• Kleene star luôn bao gồm chuỗi rỗng — không nối gì cả vẫn là một lựa chọn hợp lệ, và đó là theo định nghĩa
• Tập rỗng và chuỗi rỗng là hai kiểu đối tượng hoàn toàn khác nhau, chỉ tình cờ cùng liên quan đến "không có gì"
• Biểu thức chính quy là mô tả của ngôn ngữ, không phải bản thân ngôn ngữ — ký hiệu L(R) giữ rõ sự phân biệt đó
• Phép nối ngôn ngữ có thể tạo ra chuỗi trùng rồi bị gộp lại trong kết quả, khác với tích Descartes
• Biểu thức chính quy chỉ dùng ba phép toán và ngoặc đơn — không trừ, không giao — mà vẫn mô tả được một lớp ngôn ngữ phong phú đáng ngạc nhiên
• Loại máy đơn giản nhất (automaton hữu hạn) và biểu thức chính quy hoá ra mô tả cùng một lớp ngôn ngữ — sự tương đương đó là một trong những kết quả đẹp nhất của lĩnh vực này

Điều cuối cùng đó là thứ bài tiếp theo sẽ đào sâu. Ý tưởng rằng hai hình thức hoàn toàn khác nhau — một cái cơ học (máy đọc ký tự), một cái đại số (mẫu xây từ phép toán) — lại nắm bắt chính xác cùng tập ngôn ngữ, kết quả này khiến một lĩnh vực tưởng chừng khô khan như toán học trừu tượng bỗng trở nên sống động — giống như ta đang thực sự chạm tay vào bản chất nền tảng của tính toán vậy.