Trò chơi biển số Liên Xô và độ phức tạp Kolmogorov


Ngô Vân Hà
8 tháng trước
Hữu ích 7 Chia sẻ Viết bình luận 0
Đã xem 5828

Nhà vật lý Lev Landau từng chơi một trò chơi tinh thần với biển số xe Liên Xô. Các tấm có dạng hai chữ số, dấu gạch ngang, hai chữ số nữa và một số chữ cái.

Nội quy của trò chơi

Trò chơi của anh là áp dụng các toán tử trung học cho các số ở cả hai phía của dấu gạch ngang để dấu gạch ngang có thể được thay thế bằng một dấu bằng. Ví dụ: được cấp biển số 44-74, một giải pháp sẽ là:

4! + 4 = 7 * 4.

Lưu ý rằng chúng ta có thể chèn các toán tử, chẳng hạn như !, + Và *, nhưng không có nhiều chữ số hơn.

Có một giải pháp cho mọi tấm giấy phép có thể? Điều đó phụ thuộc vào loại toán tử mà bạn cho phép.

Bạn có thể tầm thường hóa trò chơi bằng cách áp dụng thao tác phần phân số { x } cho cả hai bên vì phần phân số của một số nguyên bằng không. Bạn có thể không cho phép toán tử phần phân đoạn với lý do đó không rõ ràng là một phép toán cấp ba, hoặc chỉ không cho phép nó vì nó làm cho trò chơi không thú vị.

Giải pháp phổ quát

Hóa ra có một giải pháp phổ quát, bắt đầu bằng việc quan sát rằng nếu một bên lớn hơn bên kia, thì công thức trên đưa ra giải pháp tức thời. Ví dụ: một giải pháp cho biển số 89-88 sẽ là:

√89 = giây arctan 88.

Nếu sự khác biệt lớn hơn, công thức có thể được áp dụng nhiều lần. Ví dụ: chúng ta có thể áp dụng công thức hai lần để có được:

( N + 2) = giây arctan ( n + 1) = giây arctan giây arctan n

và vì vậy, một giải pháp khả thi cho 35-37 là:

giây arctan giây arctan √35 = √37.

Phức tạp Kolmogorov

Cho rằng một giải pháp luôn luôn có thể, chúng ta có thể làm cho trò chơi thú vị hơn bằng cách tìm kiếm giải pháp đơn giản nhất. Chúng tôi có một số ý tưởng trực quan điều này có nghĩa là gì. Với ví dụ của chúng tôi về 44-74, giải pháp đầu tiên:

4! + 4 = 7 * 4

đơn giản hơn giải pháp phổ quát:

√74 = giây arctan giây arctan ... √44.

trong đó yêu cầu áp dụng secant và arctangent cứ sau 30 lần.

Độ phức tạp Kolmogorov của một đối tượng là độ dài của chương trình máy tính ngắn nhất để tạo ra đối tượng. Chúng ta có thể tính độ phức tạp Kolmogorov của các hàm được áp dụng cho các chữ số ở mỗi bên để đo mức độ phức tạp của một giải pháp.

Để làm cho điều này chính xác, chúng ta cần xác định ngôn ngữ lập trình của chúng ta là gì và điều đó không dễ như nói. Nếu chúng ta nghĩ ký hiệu toán học là ngôn ngữ lập trình, chúng ta có muốn đếm không! là một ký tự và arctan là 6 ký tự? Điều đó có vẻ không đúng. Nếu chúng ta viết "arctan" là "atn", chúng ta sẽ sử dụng ít ký tự hơn mà không tạo ra một giải pháp khác.

Độ phức tạp của mã Python

Để làm cho mọi thứ khách quan hơn, chúng ta có thể nhìn vào độ dài của các chương trình máy tính thực tế thay vì tưởng tượng ký hiệu toán học là ngôn ngữ lập trình. Nói rằng chúng tôi chọn Python. Sau đây là một số hàm tính toán hai giải pháp của chúng tôi cho biển số 44-74.

    from math import sqrt, cos, atan

    def f():
        sec = lambda x: 1/cos(x)
        y = sqrt(44)
        for _ in range(30):
            y = sec(atan(y))
        return y

    def g():
        return sqrt(77)

Chúng ta có thể đo độ phức tạp của các hàm fgbằng cách đếm số lượng ký tự trong mỗi hàm. Nhưng vẫn còn những khó khăn.

Còn báo cáo nhập khẩu thì sao? Nó nên được tính theo chiều dài fbởi vì nó sử dụng mọi thứ được nhập nhưng gcó thể đã sử dụng một câu lệnh ngắn hơn chỉ nhập sqrt. Về cơ bản hơn, chúng ta có gian lận bằng cách nhập thư viện không?

Hơn nữa, hai chức năng trên không tạo ra chính xác cùng một đầu ra do độ chính xác hạn chế. Chúng ta có thể tưởng tượng rằng các hàm được nhập của chúng ta là vô cùng chính xác, nhưng sau đó chúng ta không thực sự sử dụng Python mà là một phiên bản lý tưởng hóa của Python.

Và những gì về vòng lặp? Điều đó đã giới thiệu các chữ số mới, 3 và 0, và do đó vi phạm các quy tắc của trò chơi Landau. Vì vậy, chúng ta nên bỏ vòng lặp trước khi tính toán phức tạp?

Thử nghiệm tư duy

Độ phức tạp Kolmogorov là một khái niệm rất hữu ích, nhưng nó giống như một thử nghiệm tư duy hơn là thứ bạn thực tế có thể tính toán. Chúng ta có thể tưởng tượng chương trình ngắn nhất để tính toán một cái gì đó, nhưng chúng ta có thể hiếm khi biết rằng chúng ta thực sự đã tìm thấy một chương trình như vậy. Tất cả chúng ta có thể biết trong thực tế là giới hạn trên.

Về lý thuyết, bạn có thể liệt kê tất cả các máy Turing có độ dài nhất định hoặc tất cả các chương trình Python có độ dài nhất định và tìm ra máy ngắn nhất thực hiện một nhiệm vụ nhất định, nhưng danh sách tăng theo cấp số nhân theo chiều dài.

Tuy nhiên, có thể tính toán thời lượng của các chương trình cụ thể nếu chúng ta xử lý một số biến chứng được đề cập ở trên. Chúng tôi có thể biến trò chơi Landau thành trò chơi hai người bằng cách xem ai có thể đưa ra giải pháp đơn giản hơn trong một khoảng thời gian cố định.

Trở lại Landau

Nếu chúng tôi cho phép sin và bằng cấp trong tập hợp các toán tử của chúng tôi, sẽ có một giải pháp phổ quát do BS Gorobets. Với n ≥ 6, n ! là bội số của 360 và vì vậy

Và nếu n nhỏ hơn 6, thì biểu diễn hai chữ số bắt đầu bằng 0, vì vậy chúng ta có thể nhân các chữ số để có 0.

Nếu chúng tôi không cho phép các chức năng siêu việt, chúng tôi sẽ chặn lừa của Gorobets và chúng tôi có các chức năng có độ dài khách quan mà chúng tôi có thể đo lường một cách khách quan trong ngôn ngữ lập trình.

Hữu ích 7 Chia sẻ Viết bình luận 0
Đã xem 5828