[Phần 1] Liệu máy vi tính có thể thay thế con người trong việc làm Toán?

Máy tính có thể rất hữu dụng trong việc hỗ trợ con người giải các vấn đề toán học (như giúp tính nhanh hơn, tính nhiều hơn,…) nhưng liệu việc tự bản thân chúng có thể giải và chứng minh các vấn đề toán học có khả thi hay không? Thực tế đã chỉ ra là có thể nhưng ta cần xem xét phạm vi mà máy móc có thể thay thế con người là đến đâu trong thế giới toán học vô cùng phức tạp này.

Mời bạn xem tiếp phần 2 tại đây.

Định lý bốn màu

Đầu tiên phải kể đến thành quả đã đạt được cách đây gần 40 năm. Đó chính là máy vi tính có thể chứng minh được định lý bốn màu nổi tiếng. Định lý này khẳng định rằng ta có thể tô các vùng phân biệt của bất kỳ bản đồ nào với chỉ 4 màu khác nhau để làm sao cho không có hai vùng kề nhau nào có cùng màu.

Không cần nhiều hơn 4 màu để có thể tô các phần trong hình trên sao cho không có hai phần kề nhau nào cùng màu.
Không cần nhiều hơn 4 màu để có thể tô các phần trong hình trên sao cho không có hai phần kề nhau nào cùng màu.
Phiên bản 4-màu bản đồ các bang của Mỹ (bỏ qua các hồ).
Phiên bản 4-màu bản đồ các bang của Mỹ (bỏ qua các hồ).

Định lý này lần đầu tiên được chứng minh bằng máy tính là vào năm 1976, mặc dù sau đó bị phát hiện là có lỗi. Mãi đến năm 1995 thì phiên bản chính xác của chứng minh mới được cập nhật. 

Phỏng đoán Kepler minh họa bằng việc xếp các quả cam.
Phỏng đoán Kepler minh họa bằng việc xếp các quả cam.

Phỏng đoán Kepler

Năm 2003, Thomas Hales đến từ trường đại học Pittsburgh, đã cho xuất bản bài báo nói về một chứng minh số hóa cho phỏng đoán Kepler. Phỏng đoán này nói về việc sắp xếp các khối cầu trong không gian Eulclidean 3 chiều, tương tự như việc sắp một số trái cam cùng kích thước vào một cái sọt cho trước. Yêu cầu đặt ra là làm sao sắp được càng nhiều quả cam càng tốt, hay nói tổng quát hơn, với cùng một không gian cho sẵn, làm sao sắp được càng nhiều quả cầu cùng kích thước vào không gian ấy càng nhiều càng tốt.

Với những quả cầu cùng đường kính, nếu ta xem thể tích của chúng chia cho thể tích của không gian chứa là mật độ chiếm chỗ của các quả cầu thì cách xếp tối ưu nhất có thể tìm ra là mật độ bằng 74% trong khi nếu ta xếp một cách ngẫu nhiên thì đạt được khoảng 64%. Bạn có thể tham khảo thêm ở đây.

Dù Hales đã công bố chứng minh vào năm 2003 nhưng nhiều nhà toán học vẫn chưa thật sự hài lòng bởi vì chứng minh ấy đi cùng với gần 2 Gigabytes kết quả đầu ra, một con số quá lớn vào thời điểm ấy, và một số tính toán trong đó khó có thể được kiểm chứng. Để đáp trả lại, Hales lần nữa xuất bản một chứng minh tốt hơn vào năm 2014.

Bài toán logic về bộ ba số Pythagore

Kết quả gần đây nhất của việc dùng máy tính chứng minh các vấn đề toán học là bài báo vừa được đăng trên Nature (5/2016) về chứng minh số hóa của Bài toán logic về bộ ba số Pythagore (the Boolean Pythagorean triples problem). 

Bộ ba số Pythagores là bộ ba số nguyên dương a,b,c thỏa mãn a^2+b^2=c^2 phỏng theo định lý cùng tên của nhà toán học Hy Lạp lỗi lạc vốn đã quá nổi tiếng ở trường phổ thông. Khi ấy bài toán logic về bộ ba này chính là câu hỏi rằng ta có thể tô màu cho mỗi số nguyên dương với chỉ hai màu đỏ và xanh sao cho không có bất kỳ một bộ ba nào có chứa ba số cùng một màu. Ví dụ bộ ba 3,4,5 nếu 3,5 đã được tô màu xanh thì 4 phải được tô màu đỏ. 

Khẳng định ở đây chính là với các số nguyên từ 1 đến 7824, ta có thể tô màu theo quy ước ở trên với khá nhiều cách khác nhau nhưng khi mở rộng ra thêm một tí, tức nếu xét các số từ 1 đến 7825 thì việc này là không thể!

Thậm chí cho những số nguyên tương đối nhỏ, việc tìm ra một cách tô màu thỏa mãn điều kiện trên cũng không hề dễ dàng. Ví dụ như với bộ ba số 5,12,13, nếu 5 được tô màu đỏ thì một trong 12,13 phải được tô màu xanh (vì 5^2+12^2=13^2) và một trong 3,4 cũng phải được tô màu xanh tương tự (vì 3^2+4^2=5^2). Mỗi lựa chọn đều có quá nhiều ràng buộc kèm theo.

Khi xét các số từ 1 đến 7825 thì số cách mà ta có thể tô màu (không cần phải thỏa điều kiện bài toán ở trên) lên đến hàng gigantic (nhiều hơn 10^{2300} trường hợp), con số này theo sao bởi 2300 con số 0. Số trường hợp này lớn đến nỗi nếu đem xem xét với số lượng hạt cơ bản trong vũ trụ (tầm 10^{85}) thì nó vẫn còn nhiều hơn rất rất là nhiều. Điều đó cho thấy rằng nếu dùng máy tính để xem xét hết tất cả các trường hợp đó để xem có trường hợp nào thỏa yêu cầu bài toán logic bộ ba số Pythagore hay không là gần như không thể.

Những số từ 1 đến 7824 có thể được tô màu hoặc xanh hoặc đỏ để không có bất kỳ bộ ba Pythagore nào có cùng màu. Màu trắng trogn hình có thể là xanh hay đỏ đều được.
Những số từ 1 đến 7824 có thể được tô màu hoặc xanh hoặc đỏ để không có bất kỳ bộ ba Pythagore nào có cùng màu. Màu trắng trogn hình có thể là xanh hay đỏ đều được.

May mắn thay, các nhà nghiên cứu đã có thể thu hẹp số lượng các trường hợp này lại “chỉ còn” khoảng một tỉ trường hợp (trillion). Phương pháp mà họ đã dùng là ứng dụng các thành tựu của đối xứng và lý thuyết số. Từ đó, việc dùng máy tính để xem xét các trường hợp là khả thi. Các nhà khoa học đã sử dụng chiếc siêu máy tính Stampede của đại học Texas (với 800 bộ vi xử lý – processors) để chạy hết các trường hợp này trong vòng 2 ngày liên tục. Và kết quả là không thể tổ màu thỏa điều kiện của bài toán logic bộ 3 số Pythagore.

Trong khi ứng dụng thực tế của kết quả trên là không có gì thì việc cho thấy khả năng có thể giải được một bài toán tô màu phức tạp như vậy là giới hạn của các vấn đề về mã hóa và an ninh.

Chiếc siêu máy tính ở Texas được đánh giá là đã thực hiện khoảng 10^{19} các phép toán số học. Tuy nhiên con số này vẫn chưa phải là con số lớn nhất đã được một chiếc máy tính thực hiện. Vào năm 2013, tôi (GS. Jonanthan Borwein – người dịch) và các đồng sự đã tiến hành đếm số các chữ số của \pi^2 cũng bằng máy tính và số lượng tính toán thì gấp đôi con số mà siêu máy tính ở Texas đã thực hiện.

The Great Internet Mersenne Prime Search (GIMPS), một hệ thống máy tính kết nối toàn cầu cho việc tìm số chữ số sau dấu phẩy của số \pi lớn nhất có thể, đã thực hiện đều đặn tổng cộng khoảng 450 tỉ phép tính mỗi giây. Với tốc độ này, chỉ cần 6 giờ đồng hộ là có thể vượt qua số lượng tính toán của siêu máy tính ở Texas.

Kết quả thu được trong tính toán của siêu máy tính Texas có thể chiếm tới 200 terabytes, tương đương 2\times 10^{14} bytes, một con số cực khủng! Vậy thì làm sao con người chúng ta có thể kiểm chứng độ chính xác của một kết quả quá lớn về mặt kích thước như vậy? Thật sự may mắn, một giải pháp được đưa ra (minh họa bởi hình ở trên), với giải pháp này, ta có thể dùng các cách đơn giản hơn để kiểm tra.

Ý tưởng của việc kiểm tra “chia nhỏ” này cũng giống như việc phân tích một số cực lớn c nào đấy thành hai nhân tử nhỏ hơn là a,b sao cho c=a\times b vậy. Thật không đơn giản để tìm a,b, biết là thế, nhưng khi đã tìm được thì mọi việc sẽ thật đơn giản hơn nhiều.

Mời bạn xem tiếp phần 2 tại đây.

Bài viết được Đinh Anh Thi (Math2IT.com) trích dịch, biên soạn và có viết thêm một số ý dựa trên bài viết của GS. Jonathan Borwein và TS. David H. Balley.

Math2IT

Math2IT

Đây là tác giả chung cho các bài viết không do trực tiếp tác giả cụ thể nào của Math2IT viết. Có thể đó là các bài dịch từ các bài viết nước ngoài hoặc các bài viết thiên về kỹ thuật và thông báo.