Máy gửi bài

8

Máy gửi bài

Nói chung phải nói rằng đây không phải là một chiếc xe thấp chút nào. Đây là, nếu bạn thích, một bản vẽ của một cái máy. Và sẽ đúng hơn nếu nói - câu chuyện về một chiếc ô tô. Nhưng nếu bạn nói thì hãy nói trước **).

Ba mươi lăm năm trước, hai nhà khoa học xuất sắc gần như xuất hiện đồng thời trên hai tạp chí toán học (trong “Tạp chí logic tượng trưng” quốc tế xuất bản ở Hoa Kỳ và trong “Kỷ yếu của Hiệp hội toán học Luân Đôn”): Emil L. Post người Mỹ và người Anh Alain M. Tyorinen,

*) Trường được đứng đầu bởi Valentin Nikolaevich Kasatkin, tác giả của những cuốn sách nổi tiếng “The ABCs of Cybernetics” và “The Secret of Cybernetics”. Ở cuối bài viết, chúng tôi trình bày một số bài toán do anh ấy gửi.

**) Mô tả về “Máy đăng bài” ở đây thuộc về Yu. A. Gastev.

dành riêng để làm rõ khái niệm về một thuật toán (hoặc thuật toán *) đã được sử dụng từ lâu trong toán học (và không chỉ trong toán học). Thuật toán là một phương pháp chung duy nhất được thiết kế cho lời giải toàn bộ chuỗi đơn bài toán. Thống nhất - theo nghĩa là, khi biết thuật toán tương ứng, chúng ta có thể giải từng bài toán từ một chuỗi nhất định mà không cần hiểu thêm gì, như người ta nói, “hoàn toàn cơ học”, “định dạng”.

“Chính thức”, “điên rồ”, “máy móc” - những từ này thường bao hàm một ý nghĩa khá phản cảm. Và hầu như luôn luôn vô ích! Hãy tự đánh giá: việc tìm ra cách cộng bất kỳ số có nhiều chữ số nào “vào một cột” lần đầu tiên tất nhiên là khó khăn.

*) Phương pháp viết chỉ được xác định bởi truyền thống và sự hấp dẫn. Nếu chữ θ (“phyta” giống với “theta” trong tiếng Hy Lạp) được giữ nguyên trong tiếng Nga, thì mọi người sẽ tiếp tục viết “algorθm”!

10

thậm chí Gauss cũng không cần khái niệm chung về thuật toán. Nhưng để hiểu - và hơn nữa, để chứng minh rằng có những bài toán khối lượng không thể giải được (tức là các lớp bài toán không thừa nhận bất kỳ lời giải nào, thống nhất cho cả lớp *)), tất nhiên, nếu không có một định nghĩa chung như vậy, sẽ không thể thực hiện được.

Không kém phần quan trọng là giá trị thuần túy “tích cực” của khái niệm chung về một thuật toán: việc hiểu các quy luật chung chi phối các thuật toán đa dạng nhất đóng vai trò chính đối với toán học “máy”. Như đã biết, một máy tính điện tử phổ thông “có khả năng chấp nhận” các chương trình toán học đa dạng (và không chỉ toán học) bài toán**). Chương trình máy là một thuật toán, ngoài ra, chỉ được điều chỉnh phù hợp với các đặc điểm của một máy cụ thể (hoặc được viết bằng “ngôn ngữ lập trình” đặc biệt; chúng tôi cho phép “phát sóng”, tức là dịch đơn giản sang ngôn ngữ lệnh của các máy khác nhau).

Ngay từ những tác phẩm đầu tiên của Thorig và Post, dành cho việc giảng dạy khái niệm thuật toán, đã giúp đạt được những tiến bộ đáng kể theo cả hai hướng này. Động lực trực tiếp cho những nghiên cứu như vậy trong cả hai trường hợp là mong muốn thiết lập tính không thể giải được bằng thuật toán của một số bài toán khối lượng nhất định (và chính Post là người chịu trách nhiệm về những kết quả đầu tiên theo hướng này). Điều tò mò là cả hai nhà khoa học về cơ bản đều đi theo cùng một con đường (rõ ràng là con đường này không phải là con đường duy nhất).

*) Về các bài toán không thể giải được bằng thuật toán, chẳng hạn, hãy xem bài viết của F. L. Varrakhovsky và A. N. Kolmogorov “Về lời giải Các bài toán thứ mười của Hilbert” («Kvant», Số 7, 1970).

**) Ví dụ, xem bài viết của R. S. Guter “Máy móc có thể làm gì” («Kvant», Số 5, 1970) và “Ngôn ngữ của con người và ngôn ngữ của máy móc” («Kvant», Số 10, 1971).

nhưng có thể): cùng với điều có thể hiểu được bằng trực giác, nhưng hoàn toàn không phù hợp để rút ra các hệ quả toán học chính xác, nói về “một tổng quát duy nhất, được chuẩn bị cho lời giải cho cả một chuỗi cùng loại bài toán” (xem phần đầu của ghi chú này), Törig và Post đưa ra ý tưởng về một thuật toán như một loại “máy tinh thần” trừu tượng, được mô tả bằng thuật ngữ toán học chính xác và đồng thời, tương ứng với ý tưởng của chúng tôi về quá trình tính toán, diễn ra theo quy tắc-lệnh của định nghĩa của một hình thức tiêu chuẩn.

Định nghĩa chính xác nào của một thuật toán được chấp nhận - Tyoriga, Post, hoặc định nghĩa của người khác (được biết đến nhiều nhất là định nghĩa của K. Gödel, A. Church, S. K. Kleene, A. A. Markov, A. N. Kolmogorov) - không quan trọng: người ta nhanh chóng nhận ra rằng tất cả các định nghĩa này đều tương đương nhau theo nghĩa định nghĩa. Do đó, việc lựa chọn bất kỳ một trong những lời dạy này làm định nghĩa ban đầu không phải vì khía cạnh toán học của vấn đề mà để thuận tiện cho việc trình bày.

“Máy của Tyorig” được mô tả trong cả sách dịch vụ và sách phổ biến *).

“Máy Post” kém may mắn hơn về mặt này, có lẽ vì “máy” này, đơn giản hơn “máy Tyyorig”, nói chung, chính vì lý do này đòi hỏi một hệ thống lệnh cồng kềnh hơn để thực thi một bài toán cụ thể. Ngoài một bài viết duy nhất của chính Post, việc giảng dạy khái niệm thuật toán này trên thực tế chỉ được mô tả ở một nơi: trong một loạt bốn bài viết của V. A. Uspensky trên tạp chí “Matematika at School” năm 1967. Giới thiệu cho người đọc những bài viết rất thú vị (và được viết rõ ràng) này, giờ đây chúng tôi chỉ cung cấp những thông tin cơ bản nhất về “Máy Post” cần thiết để hiểu thêm.

*) Trong số những con số này, trước hết chúng tôi giới thiệu tới độc giả cuốn sách của B. A. Trakhtenbrot “Thuật toán và máy lời giải bài toán”, Fizmatiz, 1960, tái bản lần thứ 2.

12

1. máy doit thực hiện một lệnh không thể thực hiện được (in dấu trong phần bị hủy hoặc xóa dấu khỏi phần trống) - cái gọi là dừng không hiệu quả;
2. máy doit thực hiện lệnh dừng - kết quả của lệnh dừng;
3. cả hai trường hợp đầu tiên đều không thành hiện thực - máy sẽ hoạt động vô thời hạn.
   Ví dụ 1. Trong chương trình

1. ⇒2
2. ξ 3
3. dừng lại,
   áp dụng cho băng trống, việc dừng không hiệu quả sẽ xảy ra ở bước thứ hai. (vì vậy cho đến lệnh thứ ba được quy định, việc dừng kết quả vẫn chưa được thực hiện).
   Ví dụ 2. Chương trình
4. ⇒2
5. ⇒3
6. dừng lại,
   áp dụng cho một băng trống sẽ hoạt động như sau: cỗ xe sẽ di chuyển hai phần sang bên phải của phần đang được xem, sau đó máy sẽ dừng lại.
   Ví dụ 3. Nếu chương trình
7. ∨ 2
8. ⇒3
9. ⇒1
   áp dụng cho băng trống, sau đó máy sẽ in, bắt đầu từ phần đang xem, từng nhãn một và không dừng lại chút nào.
   Người đọc sẽ tìm thấy thêm những ví dụ khác trong những bức tượng đã được đề cập của V. A. Uspensky.
   Bây giờ chúng tôi sẽ nhường chỗ cho những người tham gia trường điều khiển học trẻ của “Học viện Khoa học Nhỏ”, học sinh lớp 9 của trường Bakhchisarai số 2 Natasha Kudryavskaya, Ira Lomakina và Svetlana Priz, những người sẽ kể cho bạn nghe về kinh nghiệm học lập trình bằng máy Post (công việc của chúng, ở dạng đơn giản hóa cao, sẽ tái tạo công việc của bất kỳ máy tính phổ thông hiện đại nào). Các cô gái đã thử nghiệm chương trình của mình trên một sản phẩm do một nhân viên Giáo dục Đại học sản xuất.

Trung tâm kết hợp của Viện sư phạm Simferopol với mô hình kim loại, kèm theo chìa khóa, công tắc bật tắt, phích cắm và các thuộc tính không thể thiếu khác của “máy điều khiển học”. “Băng” trong “mô hình vận hành” này bao gồm các bóng đèn điện tử (40 chiếc; vượt quá giới hạn của băng được coi là máy dừng không thành công) và các phần được đánh dấu sẽ sáng lên và các phần được đánh dấu sẽ tắt *).

Sẽ rất thú vị khi lập trình và xem cách máy giải quyết bài toán, tuân theo chương trình của bạn. Bộ đếm lệnh cho phép bạn xem lệnh nào hiện đang chạy. Đầu tiên, chương trình được viết trên giấy, sau đó, sử dụng phích cắm, nó được ghi vào trường sắp chữ của máy (mỗi lệnh có mã kép riêng). Máy hoạt động không nhanh (ở chế độ tự động) nên mọi thao tác đều được hiển thị rõ ràng; việc thực hiện chương trình có thể bị tạm dừng.

Thật thú vị khi quan sát cách máy hoạt động như nội dung của một người trong các trò chơi khác nhau. Chúng tôi quyết định bài toán và biên dịch một chương trình mà máy không thể sử dụng theo bất kỳ cách nào **). Đây là một ví dụ về một chương trình như vậy. Điều kiện trò chơi: có 26 điểm liên tiếp trên băng, điểm ngoài cùng bên trái có thể nhìn thấy bằng thẻ. Người và máy thay phiên nhau (người luôn bắt đầu trò chơi), xóa không quá bốn điểm trong lượt của mình. Người nào xóa dấu cuối cùng sẽ thua cuộc. Nếu các điều kiện

*) Chúng tôi cố tình không tập trung vào tất cả những chi tiết ấn tượng này, để không làm người đọc mất tập trung vào công việc trong ngày; Sự khác biệt giữa “mẫu điện tử của máy Bưu điện” và mô hình “giấy diêm” được mô tả ở trên gần giống như sự khác biệt giữa biên lai cửa hàng được in trên máy tính tiền điện tử hoặc thủ công và biên lai viết tay.
**) Tức là anh ta luôn thắng: tất cả những trò chơi này đều không cho phép kết quả hòa.