Bài toán của Olympic Ngôn ngữ học và Toán học lần thứ 5

9

đã chỉ ra, nói theo cách nào đó, một bài toán thuật toán không giải được. Có nhiều cách khác nhau để xác định rằng một số cuốn sách không chứa mô tả các thuật toán tính các chữ số thập phân (nếu, chẳng hạn, chúng chứa văn bản vô nghĩa hoặc nói về sự sống trên Sao Hỏa), nhưng không tồn tại một quy tắc chung nào cho phép xác định trong thời gian hữu hạn liệu một cuốn sách có chứa mô tả một thuật toán như vậy hay không.

Đến đây chúng ta kết thúc việc thảo luận về ý nghĩa có thể có của những từ đứng trong tiêu đề bài báo. Chúng tôi hơi lo rằng sau tất cả những điều đã nói, một bộ phận độc giả bắt đầu «xem xét» các tập hợp vô hạn trong việc học toán của mình, gây phiền toái cho bản thân và những người xung quanh. Vì vậy, chúng tôi sẽ đưa ra thêm vài nhận xét mà tiếc rằng ở đây chúng tôi không thể củng cố bằng các lập luận (và sẽ chỉ giới hạn ở việc dẫn các nhà chức trách). Phần lớn các nhà toán học có khả năng «xem xét» các tập hợp vô hạn bằng cách đưa vào lập luận của mình những hạn chế nhỏ, theo ý kiến của họ, bảo đảm không có mâu thuẫn. Đồng thời, dĩ nhiên, người ta phải «xem xét» những đối tượng mà một con người không thể hoàn thành việc mô tả bằng lời cho đến hết đời mình. Tuy nhiên, người ta đã xác định rằng những «xem xét» như vậy nằm ngay ở nền tảng của tòa nhà toán học được xây dựng qua nhiều thế kỷ, và số phận tiếp theo của nó cũng phụ thuộc vào chúng. Mặc dù một số nhà toán học, với mức độ nhất quán lớn hay nhỏ, cố gắng xây dựng toán học xuất phát từ những khái niệm cho phép mô tả hữu hạn, và trên con đường này đã thu được nhiều sự kiện rất có ý nghĩa, cho phép nhìn nhận nhiều điều theo một cách khác, nhưng những tuyên bố rằng sự phát triển của toán học phải diễn ra trong khuôn khổ này đã không nhận được sự ủng hộ rộng rãi. «Không ai có thể đuổi chúng ta khỏi dãy mà Cantor đã tạo ra cho chúng ta»,—một trong những nhà toán học vĩ đại nhất, David Hilbert, đã nói.

Chúng tôi đăng một trong những bài toán được đề xuất tại Olympic ngôn ngữ học và toán học truyền thống lần thứ 5 (lần đầu type vào năm 1969).

Bài toán.
Bức thư 1.

Bạn thân mến!
Một thời gian trước tôi mua hai con chó rất đẹp: một con chó chăn cừu và một con dachshund, nhưng nhanh chóng phát hiện ra rằng chúng được dạy dỗ rất kém. Vấn đề là chúng rất thích sủa. Vì vậy sống chung với chúng trong một nhà khá khó khăn. Tuy nhiên tôi không tuyệt vọng, bởi tôi đã xác định bằng kiểm tra thực tế rằng hành vi của chúng tuân theo những quy luật nhất định, không dễ hiểu nhưng không thể bác bỏ (mặc dù có thể điều này được giải thích bởi việc trước đây những con chó từng biểu diễn trong rạp xiếc), và rằng tôi có thể tác động đến chúng bằng cách chơi piano hoặc đóng chiếc đèn thật.

Trong mỗi phút mỗi con chó hoặc sủa, hoặc im lặng: chúng không biểu hiện bất kỳ sự chuyển tiếp nào. Còn hành vi của chúng trong phút tiếp theo chỉ phụ thuộc vào các sự kiện của phút trước, và sự phụ thuộc này như sau.

Trong phút tiếp theo, chó chăn cừu hành xử giống như trong phút trước: sủa hoặc im lặng, trừ khi trong phút trước đó có chơi piano và dachshund không sủa. Trong trường hợp sau, chó chăn cừu thay đổi hành vi sang ngược lại: sủa thành im lặng và ngược lại.

Còn đối với dachshund, nếu trong phút trước chiếc đèn thật đang sáng, dachshund sẽ sủa hoặc im lặng tùy theo chó chăn cừu đã sủa hay im lặng, tức là dachshund sao chép chó chăn cừu với độ trễ một phút. Tuy nhiên, nếu đèn không sáng, dachshund sẽ làm ngược lại điều mà chó chăn cừu đã làm.

Tiếp theo ở trang 25о chó chăn cừu đã làm.

Tiếp theo ở trang 25