Có một lỗ hổng ở đáy của toán học – một lỗ hổng có nghĩa là chúng ta sẽ không bao giờ biết mọi thứ một cách chính xác. Sẽ luôn tồn tại những mệnh đề đúng mà không thể chứng minh được. Hiện tại, không ai biết chính xác những mệnh đề đó là gì, nhưng có thể, chúng sẽ giống như giả thuyết “chặt cặp số nguyên tố”.
Chặt cặp số nguyên tố là các số nguyên tố chỉ cách nhau một số, ví dụ như 11 và 13, hoặc 17 và 19. Khi tiến lên trên trục số, các số nguyên tố xuất hiện ít hơn và các cặp số nguyên tố càng trở nên hiếm hoi. Tuy nhiên, giả thuyết chặt cặp số nguyên tố khẳng định rằng có vô hạn cặp số nguyên tố như vậy – bạn sẽ không bao giờ “hết” chúng. Cho đến nay, không ai chứng minh được giả thuyết này là đúng hay sai. Điều kỳ lạ ở đây là chúng ta có thể mãi mãi không biết, bởi vì đã được chứng minh rằng trong bất kỳ hệ thống toán học nào có thể thực hiện các phép tính cơ bản, sẽ luôn tồn tại những mệnh đề đúng mà không thể chứng minh được.
Trò chơi “Game of Life” của Conway
Ý tưởng đó phản ánh chính cuộc sống. Hãy xem xét “Game of Life” của Conway, được tạo ra vào năm 1970 bởi nhà toán học John Conway (người mà thật đáng buồn khi qua đời năm 2020 do COVID-19). Trò chơi được chơi trên một lưới vô hạn các ô vuông, mỗi ô có trạng thái “sống” hoặc “chết”. Chỉ có hai quy tắc:
Bất kỳ ô chết nào có đúng ba ô láng giềng sẽ “sống” lên.
Bất kỳ ô sống nào có ít hơn hai hoặc nhiều hơn ba ô láng giềng sẽ “chết”.
Sau khi sắp xếp ban đầu các ô, hai quy tắc này được áp dụng liên tục để tạo ra các thế hệ tiếp theo một cách tự động – Conway thậm chí gọi nó là “trò chơi không người chơi”. Dù quy tắc rất đơn giản, nhưng trò chơi có thể tạo ra rất nhiều kiểu hành vi khác nhau. Một số mẫu, khi xuất hiện, duy trì trạng thái ổn định; những mẫu khác dao động theo chu kỳ; có những mẫu di chuyển qua lưới (ví dụ như “glider”); và nhiều mẫu khác dần dần “tàn lụi”, trong khi không ít mẫu lại tiếp tục phát triển vô hạn thông qua việc tạo ra thêm các ô mới.
Bạn có thể nghĩ rằng, với những quy tắc đơn giản như vậy, ta có thể dự đoán được một mẫu sẽ ổn định hay sẽ phát triển không ngừng. Tuy nhiên, hóa ra câu hỏi đó là không thể trả lời – số phận cuối cùng của một mẫu trong Game of Life là “không quyết định được”, nghĩa là không có thuật toán nào có thể, trong thời gian hữu hạn, đảm bảo đưa ra câu trả lời.
Các hệ thống không quyết định và cuộc cách mạng của lý thuyết tập hợp
Liệu có điều gì đặc biệt ở Game of Life khiến nó trở nên không quyết định được? Thực ra, có rất nhiều hệ thống không quyết định được, chẳng hạn như bộ gạch Wang, một số hiện tượng trong vật lý lượng tử, hệ thống đặt vé máy bay, và thậm chí cả trò chơi Magic: The Gathering. Để hiểu được sự xuất hiện của tính “không quyết định được” ở nhiều lĩnh vực này, chúng ta cần quay ngược lại 150 năm về thời kỳ cách mạng trong toán học.
Năm 1874, nhà toán học người Đức, Georg Cantor, đã công bố một bài báo mở ra ngành lý thuyết tập hợp – một nhánh toán học mới. Một tập hợp đơn giản chỉ là một tập hợp các đối tượng được xác định rõ ràng (ví dụ, cặp giày trên đôi chân bạn, hoặc tất cả các phòng chiếu sao trên thế giới). Có một tập hợp trống (empty set) và có tập hợp chứa tất cả mọi thứ.
Cantor đã suy nghĩ về các tập hợp số, gồm số tự nhiên (các số nguyên dương như 1, 2, 3, 4, …) và số thực (bao gồm cả phân số như 1/3, 5/2 và các số vô tỷ như π, e, và √2 – tức là bất kỳ số nào có thể biểu diễn dưới dạng chuỗi số thập phân vô hạn). Ông tự hỏi: liệu có nhiều số tự nhiên hơn, hay có nhiều số thực giữa 0 và 1? Ban đầu, vì cả hai tập đều vô hạn, ta có thể nghĩ rằng kích thước của chúng bằng nhau. Để kiểm tra, Cantor đã hình dung ra việc liệt kê một danh sách vô hạn, ghép mỗi số tự nhiên với một số thực giữa 0 và 1. Mặc dù mỗi số thực có một chuỗi số thập phân vô hạn (không có “số đầu tiên”), nhưng ta có thể sắp xếp chúng theo bất kỳ thứ tự nào miễn sao đảm bảo không lặp lại và có ánh xạ một-một với các số tự nhiên.
Giả sử ta đã có danh sách hoàn chỉnh, trong đó mỗi số tự nhiên đóng vai trò như một “chỉ số” duy nhất cho mỗi số thực. Sau đó, Cantor bảo, “hãy tạo ra một số thực mới” bằng cách lấy chữ số đầu tiên của số đầu tiên rồi cộng thêm 1, lấy chữ số thứ hai của số thứ hai rồi cộng thêm 1, lấy chữ số thứ ba của số thứ ba rồi cộng thêm 1, và cứ như vậy. (Nếu chữ số nào đó là 9, thì đổi thành 8.) Quá trình này cho ra một số thực nằm giữa 0 và 1 mà khác với mọi số trong danh sách, vì nó khác ít nhất ở một chữ số (chữ số đầu khác số thứ nhất, chữ số thứ hai khác số thứ hai, …). Đây chính là “chứng minh đường chéo” của Cantor, cho thấy rằng số lượng số thực giữa 0 và 1 vượt xa số lượng số tự nhiên – nói cách khác, không phải mọi vô hạn đều có cùng kích thước. Cantor gọi những vô hạn “đếm được” và “không đếm được”, trong đó vô hạn không đếm được còn lớn hơn rất nhiều.
Sự thay đổi trong nền tảng toán học và tranh luận giữa các trường phái
Công trình của Cantor đã gây ra một cú sốc trong toán học – một lĩnh vực mà trong suốt 2000 năm, “Elements” của Euclid được coi là nền tảng. Đến đầu thế kỷ 19, Lobachevsky và Gauss đã khám phá ra hình học phi Euclid, khiến các nhà toán học phải xem xét lại nền tảng của mình. Họ nhận thấy khái niệm “giới hạn” – cốt lõi của giải tích – vốn bị định nghĩa chưa chặt chẽ, và công trình của Cantor cho thấy vô hạn còn phức tạp hơn rất nhiều so với những gì ai từng tưởng tượng.
Sự thay đổi này đã dẫn đến một cuộc tranh luận lớn vào cuối thế kỷ 19. Một nhóm gọi là “trường phái trực giác” cho rằng công trình của Cantor là vô nghĩa, khẳng định rằng toán học chỉ là sản phẩm của trí óc con người và các vô hạn như của Cantor không có thật. (Có người thậm chí dự đoán rằng các thế hệ sau sẽ coi lý thuyết tập hợp như một “căn bệnh” mà toán học đã thoát ra.) Ngược lại, “trường phái hình thức” tin rằng toán học có thể được xây dựng trên nền tảng logic vững chắc nhờ lý thuyết tập hợp. Người dẫn dắt không chính thức của nhóm này là nhà toán học người Đức David Hilbert – một huyền thoại sống, có ảnh hưởng sâu rộng trên mọi lĩnh vực toán học. Hilbert, người từng tiến gần đến việc phát triển thuyết tương đối chung trước Einstein và đã phát triển các khái niệm toán học mới thiết yếu cho cơ học lượng tử, coi công trình của Cantor là xuất sắc. Ông tin rằng một hệ thống chứng minh hình thức chặt chẽ dựa trên lý thuyết tập hợp có thể giải quyết mọi vấn đề tồn tại trong toán học. Hilbert từng tuyên bố: “Không ai được trục xuất khỏi thiên đường mà Cantor đã tạo ra.”
Nhưng vào năm 1901, Bertrand Russell đã chỉ ra một vấn đề nghiêm trọng trong lý thuyết tập hợp của Cantor. Russell nhận thấy rằng nếu các tập hợp có thể chứa bất cứ thứ gì – kể cả các tập hợp khác hoặc chính chúng – thì sẽ phát sinh những nghịch lý. Ví dụ, tập hợp của tất cả các tập hợp phải chứa chính nó, như vậy tập hợp các tập hợp có hơn năm phần tử cũng chứa chính nó. Điều này dẫn đến câu hỏi về tập hợp R gồm tất cả các tập hợp không chứa chính chúng. Nếu R không chứa chính nó thì theo định nghĩa nó phải chứa, nhưng nếu nó chứa thì nó lại không được chứa – mâu thuẫn rõ ràng. Russell đã minh họa nghịch lý tự tham chiếu này bằng một ví dụ: “Giả sử có một ngôi làng chỉ có những người đàn ông trưởng thành và có một quy định kỳ lạ rằng người cạo râu trong làng chỉ được cạo cho những người không tự cạo râu. Nhưng người cạo râu cũng là một người đàn ông trong làng, vậy ai sẽ cạo râu cho anh ta?” Nghịch lý này cho thấy vấn đề của tự tham chiếu.
Trong khi các nhà trực giác vui mừng vì nghịch lý của Russell dường như chứng minh lý thuyết tập hợp bị sai hoàn toàn, thì các nhà toán học như Zermelo và những người thuộc “trường phái Hilbert” đã giải quyết vấn đề này bằng cách giới hạn khái niệm về tập hợp – chẳng hạn như “tập hợp của tất cả các tập hợp” không còn được xem là một tập hợp nữa. Qua đó, các nghịch lý tự tham chiếu được loại bỏ, mặc dù vấn đề tự tham chiếu vẫn không dễ “diệt”.
Vấn đề gạch ngói (Wang Tiles) và tính không quyết định
Chuyển sang những năm 1960, nhà toán học Hao Wang nghiên cứu các viên gạch vuông có các màu khác nhau ở mỗi cạnh. Quy tắc là các cạnh khi tiếp xúc phải cùng màu và bạn không được xoay hay lật gạch – chỉ được trượt chúng xung quanh. Câu hỏi đặt ra là: với một tập hợp ngẫu nhiên các viên gạch như vậy, ta có thể xác định được chúng có thể lát kín mặt phẳng vô hạn mà không có khoảng trống hay không? Thực tế, đối với một tập hợp ngẫu nhiên, vấn đề “liệu các viên gạch có lát kín mặt phẳng hay không” là không thể quyết định được – giống như việc xác định số phận của một mẫu trong Game of Life, và cốt lõi của vấn đề lại đến từ tự tham chiếu.
Chương trình của Hilbert và hệ thống chứng minh hình thức
Hilbert mong muốn củng cố nền tảng của toán học bằng cách phát triển một hệ thống chứng minh mới. Ý tưởng này không mới – từ thời Hy Lạp cổ đại, hệ thống chứng minh đều bắt đầu từ các tiên đề (những mệnh đề cơ bản được giả định là đúng, ví dụ “giữa hai điểm bất kỳ luôn có thể vẽ được một đường thẳng”), sau đó xây dựng chứng minh dựa trên các quy tắc suy diễn (các phương pháp chuyển các mệnh đề đã đúng sang các mệnh đề mới cũng đúng).
Hilbert khao khát một hệ thống chứng minh hình thức – một ngôn ngữ logic ký hiệu với các quy tắc thao tác chặt chẽ – để có thể chuyển các mệnh đề toán học vào hệ thống đó. Ví dụ, “nếu bạn thả một quyển sách xuống, thì nó sẽ rơi” có thể được biểu diễn dưới dạng “a, sau đó b”; “không có con người nào bất tử” cũng được biểu diễn tương tự. Hilbert cùng các nhà hình thức đặt mục tiêu biểu diễn các tiên đề của toán học dưới dạng ký hiệu, đồng thời xây dựng các quy tắc suy diễn cho hệ thống. Bertrand Russell cùng Alfred North Whitehead đã phát triển một hệ thống hình thức như vậy trong tác phẩm “Principia Mathematica” (1913) – một bộ sách gồm gần 2.000 trang ký hiệu toán học đặc sắc, trong đó cần 762 trang mới chứng minh đầy đủ rằng 1 cộng 1 bằng 2 (với ghi chú “đề xuất trên đôi khi cũng hữu ích”). Ban đầu, họ dự định có tập thứ tư, nhưng cuối cùng vì quá mệt mỏi nên không hoàn thành. Dù hệ thống ký hiệu này rất dày đặc và đòi hỏi sự nỗ lực, nó lại mang tính chính xác tuyệt đối, loại trừ mọi lỗi sai hay sự mơ hồ, và quan trọng nhất, nó cho phép ta chứng minh các đặc tính của chính hệ thống đó.
Ba câu hỏi lớn của Hilbert và định lý bất toàn của Gödel
Hilbert đặt ra ba câu hỏi lớn cho toán học:
Toán học có đầy đủ không? – Liệu mọi mệnh đề đúng có thể được chứng minh hay không?
Toán học có nhất quán không? – Hệ thống có tránh được mâu thuẫn (ví dụ, nếu ta có thể chứng minh cả “a” và “không a”, thì ta có thể chứng minh mọi thứ, gây ra vấn đề nghiêm trọng).
Toán học có thể quyết định được không? – Liệu có tồn tại một thuật toán nào luôn xác định được rằng một mệnh đề có được suy ra từ các tiên đề hay không?
Hilbert tin rằng câu trả lời cho cả ba câu hỏi là “có”. Tại hội nghị lớn năm 1930, ông đã có bài phát biểu sôi nổi về những câu hỏi này và kết thúc bằng câu: “Chúng ta phải biết, chúng ta sẽ biết” – trái ngược với ý nghĩ của kẻ cho rằng “chúng ta sẽ không biết”. Câu nói này được khắc trên mộ của ông.
Tuy nhiên, ngay sau đó, tại một cuộc họp nhỏ cùng hội nghị, một nhà logic 24 tuổi tên Kurt Gödel đã thông báo rằng ông đã tìm ra câu trả lời cho câu hỏi về tính đầy đủ: một hệ thống hình thức đầy đủ của toán học là điều không thể. Ban đầu, chỉ có John von Neumann (một học trò của Hilbert) quan tâm và trao đổi thêm với Gödel, nhưng năm sau, Gödel đã công bố định lý bất toàn của mình, khiến cả cộng đồng toán học, kể cả Hilbert, phải chú ý.
Giải thích định lý bất toàn của Gödel
Gödel đã dùng logic và toán học để đặt câu hỏi về chính hệ thống của chúng ta. Ông gán cho mỗi ký hiệu cơ bản của hệ thống một con số, gọi là “số Gödel”. Ví dụ, ký hiệu “not” được gán số 1, “or” được gán số 2, “if then” là số 3. Khi biểu diễn các ký hiệu bằng số, số 0 cũng có số riêng, và để viết số 1, ta chỉ cần thêm ký hiệu “số kế” ngay sau 0 (với số kế của 0 là 1); để biểu diễn số 2, ta có thể viết “ss0” và cứ như vậy. Mặc dù khá rườm rà, nhưng hệ thống này cho phép ta biểu diễn bất kỳ số nguyên dương nào.
Khi đã có các số Gödel cho các ký hiệu và số cần dùng, ta có thể viết các phương trình. Ví dụ, ta có thể viết “0 = 0”, trong đó các ký hiệu có số Gödel lần lượt là 6, 5, 6, và ta có thể tạo ra một “mã số” cho phương trình đó bằng cách lấy các số nguyên tố bắt đầu từ 2, nâng số mũ của mỗi số theo số Gödel của ký hiệu tương ứng. Như vậy, 26×35×56=2432^6 \times 3^5 \times 5^6 = 24326×35×56=243 triệu – đây chính là số Gödel của phương trình “0 = 0”. Ta có thể gán một số duy nhất cho bất kỳ dãy ký hiệu nào, như một bộ bài vô hạn. Ưu điểm của cách này là ta có thể phân tích số đó ra các thừa số nguyên tố để tìm ra chính xác các ký hiệu tạo nên “mã số” đó.
Trong bộ “bộ bài” vô hạn này, sẽ có những mệnh đề đúng và những mệnh đề sai. Để chứng minh một mệnh đề đúng, ta cần dựa vào các tiên đề – các tiên đề cũng có số Gödel riêng, được tạo ra theo cùng phương pháp. Ví dụ, một tiên đề nói rằng “số kế của bất kỳ số nào xxx không bằng 0” (điều này hợp lý vì trong hệ thống này không có số âm nên số kế của một số không thể là 0). Ta có thể thay x=0x = 0x=0 để chứng minh rằng 1≠01 \neq 01=0, tạo nên một chứng minh đơn giản. “Thẻ chứng minh” này cũng nhận được số Gödel riêng, được tính theo cách như trên: dùng các số nguyên tố, nâng số 2 lên số mũ của số Gödel của tiên đề, nhân với 3 nâng số mũ của “1≠01 \neq 01=0”… Con số thu được có thể rất lớn (có thể lên đến 73 triệu chữ số nếu tính hết), nên thường được biểu diễn dưới dạng lũy thừa. Rõ ràng, các số này rất lớn, vì vậy ta có thể ký hiệu chúng bằng các chữ cái như “số Gödel a”, “số Gödel b”, “số Gödel c”, v.v.
Gödel đã làm rất nhiều công sức để tìm ra “thẻ” có nội dung “không có chứng minh cho mệnh đề có số Gödel là ggg” và con số Gödel của thẻ này lại chính bằng ggg. Điều này có nghĩa là mệnh đề nói rằng: “Thẻ này không thể được chứng minh; không có chứng minh nào tồn tại trong bộ bài vô hạn của chúng ta cho thẻ này.” Nếu mệnh đề đó sai (tức là có chứng minh), thì ta vừa chứng minh rằng “không có chứng minh”, dẫn đến mâu thuẫn, nghĩa là hệ thống toán học trở nên mâu thuẫn. Ngược lại, nếu mệnh đề đúng (không có chứng minh), thì hệ thống chứa những mệnh đề đúng nhưng không có chứng minh. Đây chính là định lý bất toàn của Gödel – nó cho thấy bất kỳ hệ thống toán học cơ bản nào có thể thực hiện các phép tính số học cơ bản đều sẽ luôn chứa các mệnh đề đúng mà không thể chứng minh được.
Ví dụ hài hước và ý nghĩa
Trong chương trình truyền hình The Office có một câu nói hài hước phản ánh nghịch lý tự tham chiếu của định lý Gödel: “Jim là kẻ thù của tôi, nhưng hóa ra Jim cũng là kẻ thù lớn nhất của chính anh ấy; và kẻ thù của kẻ thù tôi là bạn của tôi, nên Jim thực ra là bạn của tôi; nhưng vì anh ấy là kẻ thù của chính mình, kẻ thù của bạn tôi lại là kẻ thù của tôi, vậy nên Jim vẫn là kẻ thù của tôi.” Điều này cho thấy rằng “sự thật” và “khả năng chứng minh” hoàn toàn không đồng nhất. Hilbert đã sai khi nghĩ rằng mọi mệnh đề đúng trong toán học đều có thể được chứng minh. Dù ông có thể an ủi rằng ít nhất chúng ta có thể chứng minh được tính nhất quán của toán học, nhưng sau đó Gödel lại công bố định lý bất toàn thứ hai, chứng minh rằng bất kỳ hệ thống hình thức nhất quán nào cũng không thể tự chứng minh được tính nhất quán của chính nó. Tổng hợp lại, hai định lý bất toàn của Gödel cho thấy điều tốt nhất mà ta có thể hy vọng là một hệ thống toán học nhất quán nhưng không đầy đủ, và hệ thống đó không thể tự chứng minh được tính nhất quán – có nghĩa là mâu thuẫn luôn có khả năng xuất hiện trong tương lai.
Vấn đề “quyết định được” và bài toán dừng của Turing
Câu hỏi cuối cùng của Hilbert là: “Toán học có thể quyết định được không?” Hay nói cách khác, liệu có tồn tại một thuật toán nào luôn xác định được rằng một mệnh đề có được suy ra từ các tiên đề hay không? Năm 1936, Alan Turing đã tìm ra cách giải quyết vấn đề này, và để làm được điều đó, ông đã phát minh ra máy tính hiện đại.
Vào thời của Turing, “máy tính” không phải là cỗ máy mà là những con người (thường là phụ nữ) thực hiện các phép tính dài và tẻ nhạt. Turing hình dung ra một cỗ máy hoàn toàn cơ học, đủ mạnh để thực hiện bất kỳ phép tính nào nhưng lại đơn giản đến mức ta có thể lý giải được cách nó hoạt động. Máy của ông nhận đầu vào là một dải băng vô hạn gồm các ô vuông, mỗi ô chứa số 0 hoặc 1. Máy có một đầu đọc-ghi có thể đọc từng chữ số một, sau đó thực hiện một trong số ít thao tác: ghi đè giá trị mới, di chuyển sang trái, sang phải hoặc dừng lại (nghĩa là chương trình đã chạy xong). Chương trình của máy là tập hợp các hướng dẫn nội bộ, giống như một sơ đồ luồng chỉ dẫn máy làm gì dựa trên chữ số nó đọc và trạng thái nội bộ của nó. Những hướng dẫn này có thể được chuyển sang bất kỳ máy Turing nào khác để đảm bảo cùng một hành vi.
Dù ý tưởng nghe có vẻ đơn giản, nhưng với bộ nhớ và chương trình có kích thước không giới hạn, máy Turing có thể thực hiện bất kỳ thuật toán tính toán nào (từ các phép cộng, trừ cho đến các thuật toán phức tạp như của YouTube). Điều này làm cho máy Turing trở nên hữu ích trong việc trả lời câu hỏi về tính “quyết định được” của toán học. Khi máy Turing dừng, chương trình đã hoàn thành và dải băng là kết quả. Tuy nhiên, đôi khi máy Turing không bao giờ dừng – nó có thể rơi vào vòng lặp vô hạn. Liệu có thể xác định trước được một chương trình có dừng hay không trên một đầu vào cụ thể? Turing nhận ra rằng bài toán dừng này gần giống với bài toán “quyết định được”. Nếu ta có thể xác định được liệu một máy Turing có dừng hay không, thì cũng có thể xác định được liệu một mệnh đề có được suy ra từ các tiên đề hay không. Ví dụ, ta có thể “giải” giả thuyết chặt cặp số nguyên tố bằng cách viết một chương trình máy Turing khởi đầu từ các tiên đề, tạo ra các định lý theo từng bước dựa trên quy tắc suy diễn, và mỗi lần tạo ra một định lý mới, kiểm tra xem đó có phải là giả thuyết chặt cặp số nguyên tố hay không; nếu có, chương trình dừng, nếu không, chương trình chạy mãi.
Turing giả định rằng ta có thể xây dựng được một máy (gọi là H) có khả năng xác định liệu bất kỳ máy Turing nào có dừng trên đầu vào cho trước hay không. Máy H nhận vào chương trình và đầu vào của nó, sau đó “mô phỏng” hành vi và in ra “dừng” hoặc “không dừng”. Sau đó, ta sửa đổi máy H thành H⁺ bằng cách thêm quy tắc: nếu H cho kết quả “dừng” thì H⁺ ngay lập tức chuyển sang vòng lặp vô hạn; nếu H cho “không dừng” thì H⁺ dừng ngay. Tiếp theo, ta cho máy H nhận vào chính mã của nó như là đầu vào. Trong trường hợp này, H phải tự xác định hành vi của một máy mà nó cũng là một phần của nó. Nếu H kết luận rằng H⁺ sẽ không dừng, thì H⁺ sẽ dừng ngay; nếu H cho rằng H⁺ sẽ dừng, thì H⁺ lại bị buộc phải chạy vòng lặp. Điều này dẫn đến mâu thuẫn rõ ràng. Do đó, không tồn tại máy H nào có thể tổng quát xác định được liệu một máy Turing có dừng trên đầu vào cho trước hay không. Điều này có nghĩa là toán học là “không quyết định được” – không có thuật toán nào luôn có thể xác định được liệu một mệnh đề có được suy ra từ các tiên đề hay không. Như vậy, giả thuyết chặt cặp số nguyên tố (cũng như nhiều vấn đề mở khác) có thể mãi mãi là bất giải được.
Vấn đề không quyết định trong hệ thống vật lý
Vấn đề không quyết định cũng xuất hiện ở các hệ thống vật lý. Trong cơ học lượng tử, một trong những đặc tính quan trọng của hệ thống nhiều hạt là hiệu số năng lượng giữa trạng thái cơ bản và trạng thái kích thích đầu tiên, gọi là “spectral gap.” Một số hệ thống có khoảng cách năng lượng đáng kể, trong khi hệ thống khác lại “không có khoảng cách” (có dải năng lượng liên tục kéo dài đến trạng thái cơ bản). Điều này quan trọng vì ở nhiệt độ thấp, các hệ thống lượng tử không có khoảng cách có thể trải qua chuyển pha, trong khi các hệ thống có khoảng cách thì không, do không đủ năng lượng để vượt qua nó. Việc xác định liệu một hệ thống có “khoảng cách” hay “không khoảng cách” đã từ lâu được coi là bài toán rất khó, và chỉ đến năm 2015, các nhà toán học mới chứng minh rằng vấn đề spectral gap nói chung là không quyết định được. Theo các tác giả, ngay cả một mô tả hoàn hảo về tương tác vi mô giữa các hạt cũng không đủ để suy ra được các tính chất vĩ mô của vật chất.
Tính đầy đủ theo tiêu chuẩn Turing
Hãy nhớ rằng Turing đã thiết kế máy của mình để có sức mạnh tính toán tối đa. Cho đến ngày nay, những hệ thống tính toán xuất sắc nhất là những hệ thống có thể thực hiện mọi thao tác mà một máy Turing có thể làm – gọi là “Turing complete.” Tuy nhiên, mỗi hệ thống Turing-complete đều đi kèm với một vấn đề “dừng” tương tự – tức là có một tính chất không quyết định được. Ví dụ, với bộ gạch Wang, bài toán dừng là liệu các viên gạch có thể lát kín mặt phẳng hay không; với các hệ thống lượng tử phức tạp, bài toán dừng liên quan đến spectral gap; và trong Game of Life, bài toán dừng chính là việc liệu trò chơi có dừng lại hay không. Ngoài ra còn có rất nhiều ví dụ khác như hệ thống đặt vé máy bay, trò chơi Magic: The Gathering, bài thuyết trình PowerPoint hay bảng tính Excel. Hầu như mọi ngôn ngữ lập trình hiện nay đều được thiết kế để “Turing complete”, mặc dù về lý thuyết chỉ cần một ngôn ngữ là đủ để lập trình bất cứ thứ gì. Ví dụ, ngay trong Game of Life cũng có thể chạy một máy Turing; vì Game of Life vốn là hệ thống Turing complete nên nó có khả năng mô phỏng lại chính nó – và thực tế, nó làm được điều đó.
Di sản của Hilbert và Turing
Di sản thực sự của giấc mơ Hilbert chính là tất cả các thiết bị tính toán hiện đại ngày nay. Kurt Gödel sau này đã trải qua những cơn bất ổn tinh thần, tin rằng người khác đang cố gắng đầu độc ông, và cuối cùng tự đói cho đến khi qua đời. Hilbert mất năm 1943, với dòng chữ “Chúng ta phải biết, chúng ta sẽ biết” được khắc trên mộ của ông. Sự thật là, có những điều chúng ta không biết – đôi khi chúng ta không thể biết được. Nhưng trong quá trình tìm hiểu, ta lại khám phá ra những điều mới mẻ, những điều đã thay đổi cả thế giới. Alan Turing đã đưa ý tưởng tính toán của mình vào thực tiễn trong Thế chiến II, dẫn dắt đội ngũ tại Bletchley Park xây dựng các máy tính thực thụ để phá mã của Đức quốc xã, rút ngắn chiến tranh từ 2 đến 4 năm. Sau chiến tranh, Turing cùng John von Neumann đã thiết kế ra máy tính điện tử lập trình được đầu tiên – ENIAC – dựa trên những ý tưởng của Turing. Tuy nhiên, Turing không kịp chứng kiến những phát triển sau này: năm 1952, chính phủ Anh kết án ông vì “hành vi khiếm khuyết đạo đức” khi phát hiện ông là người đồng tính, tước bỏ quyền truy cập an ninh và buộc ông dùng hormone, và năm 1954 ông đã tự kết liễu đời mình. Turing đã thay đổi cả thế giới – ông được coi là nhân vật sáng lập quan trọng nhất của ngành khoa học máy tính, khi mọi máy tính hiện đại đều có nguồn gốc từ thiết kế của ông. Ý tưởng của Turing về tính toán bắt nguồn từ khái niệm “máy Turing”, được hình thành khi ông suy nghĩ về câu hỏi của Hilbert: “Toán học có thể quyết định được không?” Như vậy, các máy phá mã của Turing và tất cả máy tính hiện đại đều bắt nguồn từ những nghịch lý kỳ lạ phát sinh từ tự tham chiếu.
Kết luận
Có một lỗ hổng ở đáy của toán học – một lỗ hổng có nghĩa là chúng ta sẽ không bao giờ biết mọi thứ một cách chính xác. Sẽ luôn tồn tại những mệnh đề đúng mà không thể chứng minh được. Bạn có thể nghĩ rằng nhận thức này sẽ khiến các nhà toán học phát điên và dẫn đến sự sụp đổ của toàn bộ ngành toán, nhưng thay vào đó, việc suy nghĩ về vấn đề này đã biến đổi khái niệm về vô hạn, thay đổi cả diễn tiến của một cuộc chiến tranh toàn cầu và trực tiếp dẫn đến việc phát minh ra thiết bị mà bạn đang sử dụng để xem video này.
