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

Một trong các bài tập rất hay cho người đang học lập trình (bất kể ngôn ngữ nào) là: hãy viết một chương trình in chính nó ra. Chú ý là phải in ra giống hệt, từng giòng từng chữ từng cái xuống hàng. Ở đây ta giả sử có thể viết chương trình bằng một tệp (file) thôi.

Nếu bạn chưa bao giờ nghĩ về các chương trình kiểu này, hãy dành vài chục phút nghĩ trước khi đọc các ví dụ dưới đây. Bạn sẽ thấy bài tập này liên quan mật thiết đến khái niệm "tự tham chiếu", một trong những khái niệm trung tâm trong bài Chung qui chỉ tại Cantor.

Thử xét vài ví dụ sau:

main(){char *c="main(){char *c=%c%s%c;printf(c,34,c,34);}";printf(c,34,c,34);}
import java.text.*;class a{public static void main(String x[]){char b[]={34};
char c[]={123};String s[]=new String[3];s[0]="import java.text.*;class a{2}
public static void main(String x[]){2}char b[]={2}34};char c[]={2}123};
String s[]=new String[3];s[0]={1}{0}{1};s[1]=new String(b);s[2]=new String(c);
System.out.println(MessageFormat.format(s[0],s));}}";s[1]=new String(b);s[2]=
new String(c);System.out.println(MessageFormat.format(s[0],s));}}
((lambda (x)
(list x (list (quote quote) x)))
(quote
(lambda (x)
(list x (list (quote quote) x)))))
#!/usr/bin/perl
$_=<<'eof';eval $_; print "#!/usr/bin/perl\n\$_=<<'eof';eval \$_;\n${_}eof\n" 
eof


Các ví dụ trên tôi lấy ở đây, và ở đây. Dưới đây ta sẽ thiết kế một ví dụ cho riêng ta, không cần đi "chôm" về. Các trương trình tự in bản thân còn được gọi là Quine, họ của triết gia Willard van Orman Quine. Có hai câu hỏi liên quan:

  1. Có nguyên tắc gì để viết các chương trình lọai này không? Cho một ngôn ngữ mới thì làm thế nào ta viết được một chương trình như vậy?
  2. Các chương trình lọai này có ứng dụng gì không?

Trước hết, ta bàn về nguyên tắc viết các chương trình tự in được bản thân. Ta sẽ làm việc trên một mô hình tổng quát (nhưng hoàn có thể hiện thực được với bất kỳ ngôn ngữ máy tính nào). Giả sử trong mô hình máy tính này có một vùng nhớ mà tất cả các chương trình đều lấy input từ đó và ghi ra đó được. Có hai quan sát nhỏ:

  1. Cho một chuỗi x bất kỳ, ví dụ x = "học như nghịch thủy hành châu", gọi P(x) là chương trình ghi x vào vùng nhớ chung. Có thể có nhiều P(x) khác nhau, ta cứ thống nhất một loại P(x) duy nhất. Bạn có thể nghĩ đến phát biểu
strcpy(buffer, "Học như nghịch thủy hành châu");

trong ngôn ngữ C chẳng hạn.

  1. Cho một chuỗi x bất kỳ trong vùng nhớ, ta có thể dễ dàng viết một đoạn chương trình sẽ ghi P(x) vào vùng nhớ.

Ý tưởng của chương trình tự in bản thân (vào vùng nhớ chung) như sau: chương trình này có hai đoạn, đoạn A và đoạn B, nghĩa là nối A với B thì ta có toàn bộ chương trình.

Đoạn B làm công việc như sau:

  1. x = chuỗi các bytes trong vùng nhớ
  2. Ghi P(x) vào vùng nhớ
  3. Ghi x vào vùng nhớ

Chú ý rằng, sau khi B hoạt động xong thì trong vùng nhớ chung chứa P(x) rồi đến x. Bạn nên tưởng tưởng viết một đoạn chương trình như B trong ngôn ngữ bạn thích.

Đoạn chương trình A thì làm gì? Nó sẽ ghi x vào vùng nhớ cho B đọc và ghi P(x), x. Thế A ghi gì? A ghi ra chính đoạn B ở trên!!!

Vì A ghi B vào vùng nhớ, A = P(B), và x = B. Còn B ghi ra "P(x)x" = "P(B)B" = "AB", chính là chương trình ta đang viết.

 

Ta thử dùng nguyên tắc mô tả trong ví dụ trước để viết một chương trình C tự in bản thân. Lần thử đầu tiên, chương trình A ghi x vào biến buffer, chương trình B in ra đoạn chương trình P(x), sau đó in x. Kết quả đại khái như sau:

int main() {
 char* buffer = "printf(\"int main() {\\n char* buffer = %s;\\n %s\\n}\\n\", buffer, buffer);";
 printf("int main() {\n char* buffer = \"%s\";\n %s\n}", buffer, buffer);
}

Lần thử này không thành công lắm, dù chương trình này in ra một chương trình gần giống nó. Vấn đề nằm ở cả đống ký tự thoát (escape characters '\'). Nó in thế này:

int main() {
 char* buffer = "printf("int main() {\n char* buffer = %s;\n %s\n}\n", buffer, buffer);";
 printf("int main() {\n char* buffer = %s;\n %s\n}\n", buffer, buffer);
}

Rút kinh nghiệm, tôi tránh các escape characters và thay chúng bằng mã ASCII. Mã ASCII của ký tự xuống dòng (linefeed) là 10, và của ký tự ngoặc kép (") là 34. Kết quả lần thử thứ hai cho đoạn chương trình:

int main() {
 char* buffer = "printf(\"int main() {%c char* buffer = %c%s%c;%c %s%c}\", 10, 10, 34, buffer, 34, 10, buffer, 10);";
 printf("int main() {%c char* buffer = %c%s%c;%c %s%c}", 10, 34, buffer, 34, 10, buffer, 10);
}

Chương trình này in ra

int main() {
 char* buffer = "printf("int main() {%c char* buffer = %c%s%c;%c %s%c}", 10, 10, 34, buffer, 34, 10, buffer, 10);";
 printf("int main() {%c char* buffer = %c%s%c;%c %s%c}", 10, 10, 34, buffer, 34, 10, buffer, 10);
}

Giống lắm rồi. Nhưng vẫn bị một escape character \ cho dấu " của printf. Lý do là vì cả printf lẫn định nghĩa buffer đều dùng ", mà nếu bỏ " vào trong định nghĩa buffer thì phải escape nó. Nhưng ta hoàn toàn có thể printf mà không dùng " như sau:

int main() {
 char* buf1 = "char buf2[] = {'i', 'n', 't', ' ', 'm', 'a', 'i', 'n', '(', ')', ' ', '{', '%', 'c', ' ', 'c', 'h', 'a', 'r', '*', ' ', 'b', 'u', 'f', '1', ' ', '=', ' ', '%', 'c', '%', 's', '%', 'c', ';', '%', 'c', ' ', '%', 's', '%', 'c', '}', (char) 0}; printf(buf2, 10, 34, buf1, 34, 10, buf1, 10);";
 char buf2[] = {'i', 'n', 't', ' ', 'm', 'a', 'i', 'n', '(', ')', ' ', '{', '%', 'c', ' ', 'c', 'h', 'a', 'r', '*', ' ', 'b', 'u', 'f', '1', ' ', '=', ' ', '%', 'c', '%', 's', '%', 'c', ';', '%', 'c', ' ', '%', 's', '%', 'c', '}', (char) 0}; printf(buf2, 10, 34, buf1, 34, 10, buf1, 10);
}

Bạn có thể dịch và chạy thử đoạn trên, in ra chương trình y hệt.

 

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):

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?

 

Ta đã "chứng minh" rằng mọi chương trình có thể lấy được đoạn mã của chính nó. (Chứng minh điều này một cách chặt chẽ bằng toán học cũng không có gì khó khăn, tương tự như các ý tưởng ta đã trình bày, chỉ cần định nghĩa rõ ràng thế nào là một chương trình.) Phát biểu này thường được gọi là định lý đệ qui (recursion theorem).

Đến đây, ta minh họa một ứng dụng của định lý đệ qui. Ta sẽ dùng định lý này để chứng minh rằng bài toán dừng không quyết định được. Tôi sẽ thảo luận ý tưởng chính, bỏ qua các chi tiết toán không quan trọng. Bài toán dừng đại khái có thể phát biểu như sau: "cho một đoạn mã chương trình [M] và một chuỗi w, quyết định xem với input w thì M có dừng sau một số hữu hạn các bước hay không?" (Ta dùng [M] để chỉ đoạn mã của chương trình M.)

Định lý: không tồn tại chương trình nào giải bài toán dừng.

Chứng minh: giả sử có chương trình A giải bài toán dừng, ta thiết kế một chương trình M để làm phản chứng như sau

  1. Gọi input của M là w
  2. M tự lấy đoạn mã [M] của chính nó
  3. M chạy A với input là ([M], w).
  4. Nếu A trả lời là "dừng" thì M nhảy vào một vòng lặp vô tận.
  5. Nếu A trả lời là "không dừng" thì M dừng.

Như vậy A không thể nào quyết định xem M có dừng hay không!

Chứng minh trên rất đặc trưng cho lập luận đường chéo của Cantor, thường được dùng cho các bài toán mà đối tượng có tính tự tham chiếu. Lý luận kiểu như trên là một trong những công cụ rất mạnh để chứng minh phản chứng trong lý thuyết tính toán.

Không biết các bạn thế nào chứ lúc đầu tôi thấy việc thiết kế chương trình tự in khá là phản trực quan. (Tưởng tượng một nhà máy sản xuất gỗ lại có thể sản xuất một nhà máy sản xuất gỗ y hệt như nó.) Thế mà câu trả lời không những là có các chương trình như vậy, mà còn có cả một nguyên tắc viết các chương trình đó.

Trong bài này, ta đã đi từ một câu hỏi tự tham chiếu này (chương trình tự in) sang câu hỏi tự tham chiếu khác (bài toán dừng). Ta dùng câu trả lời có cho câu hỏi đầu để trả lời không cho câu hỏi thứ hai.

 

10/04/2005

NQH