Chương trình tự tái sinh (4)

Chương trình tự tái sinh có nhiều ứng dụng thú vị. "In bản thân" chỉ là một ví dụ của sự tái sinh.

Các virus máy tính đều có chức năng tái sinh "y chang" này, nhưng thay vì in ra stdout, chúng tự copy bản thân qua một địa chỉ mới (trong bộ nhớ, qua mạng, hay xuống đĩa cứng). Trong bài tiến hóa số tôi có đề cập đến các chương trình máy tính tự tái sinh dùng để mô phỏng tiến hóa của các loại "vi khuẩn số" đơn giản.

Trong tương lai, bạn có thể tưởng tượng các chương trình phức tạp hơn, hay các robots tự tái sinh. Hy vọng đến đây bạn đã được thuyết phục rằng sự tự tái sinh không phải là thứ vô vọng về mặt triết học.

Trong các ví dụ trước, ta chỉ thiết kế các chương trình có chức năng duy nhất là in ra bản thân. Còn bọn "vi khuẩn số" hay viruses còn làm các việc khác nữa. Chuyện này không có gì khó. Giả sử ta có chương trình T làm việc gì đó (phá đĩa cứng chẳng hạn), ta có thể thiết kế chương trình ABT bao gồm đoạn A = P( x), đoạn B giống như trước, và đoạn T. Thay vì A ghi x = B vào vùng nhớ, thì trong trường hợp này A sẽ ghi x = BT, còn B thì in P(x)x như cũ. Như vậy ta đã bổ túc cho chương trình T chức năng tự tái sinh mà không cần suy nghĩ gì nhiều.

Cái mô hình máy có bộ vi xử lý truy cập một vùng nhớ chung của ta chính là mô hình máy Turing. Lần tới ta sẽ dùng ý tưởng về sự tự tái sinh này để chứng minh rằng có bài toán không quyết định được bằng máy Turing (xem thêm chung qui chỉ tại Cantor). Như đã nói trong bài "chung qui chỉ tại Cantor", khái niệm tự tham chiếu là một khái niệm then chốt. Vì thế, cũng không ngạc nhiên lắm khi sự tự tái sinh có liên quan đến vấn đề không quyết định được.

Bài tập 1 : viết một chương trình C chép file X sang file Y, sau đó tự in bản thân nó (C) ra stdout.

Để minh họa khái niệm tự in và tự tham chiếu một lần nữa, hãy xét ví dụ sau (tôi lấy ở đây):

• This sentence has three a's, two c's, two d's, twenty-eight e's, four f's, four g's, ten h's, eight i's, two l's, eleven n's, six o's, seven r's, twenty-seven s's, eighteen t's, three u's, five v's, six w's, three x's, and three y's.

Bài tập 2 : viết một chương trình C tìm một câu tiếng Việt có nội dung tương tự.

Bài tập 3: có phải tất cả các ngôn ngữ đều có một câu dạng này hay không? Ngôn ngữ với tính chất gì thì có một câu như vậy?