\\ Các mục của Tạp chí USP
Vẻ đẹp của toán học
Cláudio Possani, Flávio Ulhoa CoelhovàMarcelo Fingergiáo viên của Viện Toán học, Thống kê và Khoa học Máy tính của USP
nhân vật chính trong câu chuyện là Alan Turing, người đã là nhân vật trong một bộ phim Hollywood mang tênThe Imitation Gamevà có một giải thưởng khoa học máy tính mang tên ông, Giải Turing, được trao hàng năm cho một nhà nghiên cứu đã có thành tích nổi bật trong lĩnh vực này. Năm 1937, ông đã chứng minh một cách toán học rằng có những vấn đề không thể giải quyết bằng máy tính. Tuy nhiên, để làm được điều này, ông phải định nghĩa "có thể tính toán" là gì, và trong quá trình đó, ông đã tạo ra Máy tính Turing. Những máy này là các khái niệm toán học trừu tượng, làm rõ khái niệm tính toán, và một kết quả toán học quan trọng mà ông khám phá ra cho thấy có một máy đặc biệt, gọi là Máy tính Turing tổng quát, đóng vai trò trung tâm trong Lý thuyết Tính toán. Máy tính Turing tổng quát là nền tảng cho việc xây dựng các máy tính như chúng ta biết ngày nay.
Bài viết ban đầu của Turing có một số điều thu hút sự chú ý và có mặt ngay trong tiêu đề của bài viết, được dịch tự do như sau:Về các số có thể tính toán và một ứng dụng cho bài toán ra quyết địnhNhư vậy, "số có thể tính toán" có nghĩa là có những số không thể tính toán?
Đúng vậy, và điều này không khó để nhận ra. Nhưng trước hết, hãy quay lại một chút thời gian, vì những khởi đầu của tính toán gắn liền chặt chẽ với các số vô hạn. Năm 1874, nhà toán học người Đức Georg Cantor đã xuất bản một bài viết cho thấy có nhiều loại vô hạn. Cụ thể, ông đã chứng minh rằng vô hạn của các số tự nhiên 0,1,2,3,... nhỏ hơn vô hạn của các số thực. Có lẽ bạn đã nhận ra điều này, chỉ từ một hình vẽ đơn giản. Vô hạn của các số thực tương ứng với một đường thẳng liên tục (tập hợp này được gọi là Liên tục), và trên đường thẳng này, một cách có khoảng cách, chúng ta có thể chèn các số tự nhiên hoặc các số nguyên (kích thước của vô hạn của các số này được gọi là Đếm được). Với một chiến lược rất sáng tạo, Cantor đã chứng minh rằng không thể sắp xếp các phần tử của Liên tục theo thứ tự, luôn còn một số không được sắp xếp. Như vậy, ông đã chứng minh rằng Liên tục lớn hơn các số đếm được.
Sau đó, Turing chứng minh rằng có những số thực không thể tính toán. Các số không thể tính toán luôn là các phần tử của Tập liên tục. Theo định nghĩa của ông, một số thực là có thể tính toán nếu có một chương trình hoặc, trong phiên bản gốc, một Máy Turing, in vô hạn các chữ số của nó. Nhưng mỗi chương trình và mỗi Máy Turing đều có kích thước hữu hạn và được lưu trữ trong một tệp. Một tệp chỉ là một số tự nhiên, có thể rất lớn. Vì vậy, số lượng chương trình tối đa là một vô hạn đếm được, và không thể có đủ chương trình để in tất cả các số thực. Nhiều số thực không thể được in bởi bất kỳ chương trình nào, và đây là các số thực không thể tính toán. Và chúng ta hiện biết rằng hầu hết các số thực không thể tính toán, chỉ một tỷ lệ nhỏ có thể được in bởi một chương trình hoặc một Máy Turing.
Một tin đồn nhỏ ở đây. Khi Turing viết bài báo năm 1936, mà không biết, một nhà toán học nổi tiếng khác, tên là Alonzo Church, đã chứng minh sự tồn tại của các số không thể tính toán, bằng các kỹ thuật rất khác. Vì vậy, các biên tập viên của tạp chí đã hoài nghi liệu bài báo của Turing có thực sự là gốc hay không. Bài báo nằm trên bàn trong một thời gian cho đến khi có ai đó đề xuất cho trình bày bài báo này cho chính Church, người đã thấy ý tưởng của Turing rất sáng tạo và mời ông làm học bổng tại Hoa Kỳ. Vì sự chậm trễ này, bài báo chỉ được xuất bản vào năm 1937. Turing hoàn thành bằng cấp thạc sĩ trong một năm và trở về Anh khi Chiến tranh Thế giới thứ hai nổ ra. Đó là lúc câu chuyện của bộ phim bắt đầu.Trò chơi mô phỏngSau khi Turing đã đóng góp lớn cho lịch sử của Khoa học Máy tính hiện đại.
Quay trở lại các số, phản ứng đầu tiên của mọi người khi học rằng có các số không thể tính toán là: "Xin hãy cho tôi một ví dụ về một số không thể tính toán". Và tôi, vui vẻ trả lời: "Tôi không thể cho bạn thấy. Nếu tôi cho bạn thấy số đó, tôi đã tính toán nó rồi. Và một số không thể tính toán không thể được tính toán. Rõ ràng, phải không? Chà, nếu không rõ ràng, hãy làm quen với ý tưởng rằng bạn sẽ không bao giờ có thể nhìn thấy một số không thể tính toán, chính vì nó không thể tính toán".
Nhưng nếu số đó không thể đếm được, chúng ta định nghĩa nó như thế nào? Chúng ta cần sử dụng các cách định nghĩa số không đếm được mà không cần tính toán. Một ví dụ nổi tiếng là "xác suất của một chương trình máy tính dừng". Cụm từ này được đặt trong dấu ngoặc kép là định nghĩa của số. Chúng ta chứng minh rằng đây là một số không đếm được mà chúng ta không thể biết hầu hết các thuộc tính của nó. Chúng ta không thể biết liệu số này có nhỏ hơn 0,5 hay lớn hơn 0,00000001. Tất cả những câu hỏi này cũng là những câu hỏi không đếm được.
Điều này đưa chúng ta trở lại bài viết ban đầu của Alan Turing. Ông đã chứng minh rằng có những vấn đề không thể tính toán, tức là không thể được giải quyết bởi bất kỳ Máy Turing nào, bao gồm cả Vấn đề Quyết định (từ logic bậc nhất) mà ông đề cập trong bài viết.
Và thế là, tính toán hiện đại ra đời, cho thấy tính toán có giới hạn. Có những thứ mà sẽ không bao giờ có thể tính toán, và chúng ta phải sống trong giới hạn của những gì có thể thực hiện với một máy tính. Định lý Turing không phụ thuộc vào bất kỳ ngôn ngữ lập trình hoặc loại máy tính nào. Do đó, các vấn đề không đếm được vẫn không thể đếm được với bất kỳ công nghệ nào, ngay cả với trí thông minh nhân tạo hiện đại nhất hoặc các công nghệ sẽ được phát minh trong hơn một thế kỷ nữa.
________________(Ý kiến được thể hiện trong các bài viết được đăng trênTạp chí USPHoàn toàn chịu trách nhiệm về nội dung, không phản ánh quan điểm của tòa soạn hoặc quan điểm của Viện Đại học São Paulo. Truy cập tại đây để biết cáctiêu chí biên tập cho các bài viết quan điểm.)
