Tạo mọi hàm sơ cấp từ một toán tử nhị phân duy nhất

 (arxiv.org)
7 điểm bởi GN⁺ 8 ngày trước | 2 bình luận | Chia sẻ qua WhatsApp
  • Đã chỉ ra rằng một toán tử nhị phân đơn dạng exp(x) − ln(y), gọi là EML, có thể tạo ra mọi hằng số và hàm sơ cấp
  • Chỉ với toán tử này và hằng số 1, có thể biểu diễn toàn bộ phép toán số học, các hàm siêu việt (sin, cos, log, √, v.v.), và các hằng số phức (e, π, i)
  • Mọi biểu thức EML đều được cấu thành từ cây nhị phân có cùng cấu trúc nút, nên có thể ứng dụng cho hồi quy ký hiệu và học dựa trên gradient
  • EML là đối ứng toán học của cổng NAND, đóng vai trò toán tử phổ quát duy nhất trong toán học liên tục
  • Phát hiện này cho thấy mọi hàm sơ cấp có thể được quy về một quy tắc sinh duy nhất, mở ra những khả năng mới cho khám phá công thức và AI ký hiệu

Định nghĩa của toán tử nhị phân đơn EML

  • Đã chỉ ra rằng một toán tử nhị phân đơn dạng eml(x, y) = exp(x) − ln(y) có thể tạo ra mọi hàm sơ cấp
    • Chỉ với toán tử này và hằng số 1, có thể biểu diễn toàn bộ phép toán số học (+, −, ×, /, lũy thừa), các hàm siêu việt (sin, cos, log, √, v.v.), và các hằng số (e, π, i)
    • Ví dụ, có thể biểu diễn e^x = eml(x, 1) và ln x = eml(1, eml(eml(1, x), 1))
  • Toán tử EML (Exp–Minus–Log) thực hiện tính toán trên miền số phức (C)
    • Hằng số 1 có vai trò trung hòa hạng log thông qua ln(1)=0
    • Có thể tạo ra các hằng số phức như i và π thông qua phép tính ln(−1)
  • Toán tử này được giới thiệu như toán tử cơ bản duy nhất của toán học liên tục, tương ứng với cổng NAND trong logic số
    • Giống như NAND cấu thành toàn bộ logic Boolean, EML cấu thành mọi hàm sơ cấp

Khái niệm máy tính dựa trên một toán tử duy nhất

  • Đề xuất khái niệm “máy tính hai nút”
    • Chỉ với một toán tử nhị phân (EML) và một hằng số (1), có thể thực hiện mọi chức năng của máy tính khoa học
    • Ngay cả khi không có thêm toán tử nào khác, vẫn có thể tính mọi hàm sơ cấp thực và phức
  • Không thể tiếp tục giảm số lượng toán tử hơn nữa
    • Tối thiểu phải có một toán tử nhị phân và một ký hiệu đầu cuối (hằng số)

Đặc trưng cấu trúc của biểu diễn EML

  • Mọi biểu thức EML đều có cấu trúc cây nhị phân gồm các nút đồng nhất
    • Dạng ngữ pháp: S → 1 | eml(S, S)
    • Điều này có thể được diễn giải như một ngôn ngữ phi ngữ cảnh đẳng cấu với cấu trúc Catalan và cây nhị phân đầy đủ
  • Cấu trúc đồng nhất này cho phép áp dụng tối ưu hóa dựa trên gradient (Adam, v.v.) trong hồi quy ký hiệu (symbolic regression)
    • Có thể dùng cây EML như một mạch có thể học được, và khôi phục chính xác các hàm sơ cấp dạng đóng ở độ sâu cây nông (tối đa 4)
    • Nếu quy luật sinh là một hàm sơ cấp, các trọng số đã học có thể hội tụ về đúng dạng công thức

Quá trình phát hiện và hàm ý toán học

  • Toán tử EML được phát hiện thông qua tìm kiếm vét cạn có hệ thống (exhaustive search)
    • Kết quả tìm kiếm xác nhận rằng EML tạo thành nền tảng phép toán hoàn chỉnh của máy tính khoa học
  • Nghiên cứu sử dụng cách tiếp cận “máy tính bị hỏng” (broken calculator) nhằm giảm dần số lượng toán tử
    • Thu gọn từ 4 → 3 → 2 → 1 toán tử trong khi vẫn giữ đầy đủ chức năng
  • EML có tính đơn giản ngoài dự đoán, đồng thời là toán tử nhị phân được định nghĩa bằng chính các hàm sơ cấp
  • Sự tồn tại của EML cho thấy các hàm sơ cấp thuộc về một tầng sinh đơn giản hơn rất nhiều
    • Mở rộng khả năng quy nhiều hàm khác nhau về tổ hợp của exp và ln
  • Vì có thể biểu diễn mọi công thức toán học bằng một thành phần lặp lại duy nhất,
    • nên có thể xây dựng biểu diễn mạch của công thức toán học tương tự cấu trúc dựa trên transistor trong mạch điện tử
  • Biểu diễn mạch đồng nhất này mở ra những khả năng mới cho khám phá, đánh giá và học công thức

Các khái niệm liên quan và bối cảnh lịch sử

  • Tính phổ quát của một phần tử cơ bản duy nhất là khái niệm quan trọng trong toán học, kỹ thuật và sinh học
    • Ví dụ: cổng NAND/NOR, hàm kích hoạt ReLU, toán tử tổ hợp K,S, OISC(SUBLEQ), cellular automaton Rule 110, v.v.
  • Phần tử kiểu Sheffer là rất hiếm, và việc phát hiện chúng đòi hỏi thời gian, tính toán và cả may mắn
    • EML được đưa ra như một ví dụ về toán tử liên tục kiểu Sheffer như vậy
  • Nghiên cứu dựa trên các quan hệ rút gọn đã biết như khả năng biểu diễn qua lại giữa log và mũ (x×y = e^{ln x + ln y}, x+y = ln(e^x × e^y)) và công thức Euler (e^{iφ} = cos φ + i sin φ)

Tập hàm sơ cấp và mở rộng trong tương lai

  • Nghiên cứu lấy tập hàm sơ cấp ở mức máy tính khoa học làm điểm khởi đầu
    • Hằng số: π, e, i, −1, 1, 2, x, y
    • Hàm đơn biến: exp, ln, inv(1/x), minus(−x), √, sqr(x²), σ(1/(1+e^−x)), sin, cos, tan, arcsin, arccos, arctan, sinh, cosh, tanh, v.v.
    • Phép toán nhị phân: +, −, ×, /, log, pow(x^y), avg((x+y)/2), hypot(√(x²+y²))
  • Đã chứng minh rằng toàn bộ tập này có thể được thay thế hoàn toàn bằng toán tử EML duy nhất và hằng số 1
  • Trong quá trình tìm kiếm ban đầu, các toán tử tương tự có tính chất còn mạnh hơn cũng đã được phát hiện
    • Ví dụ: toán tử biến thể tam nguyên (ternary) không cần hằng số
  • EML được xem như điểm khởi đầu cho khả năng tồn tại của toán tử sinh duy nhất trong toán học liên tục
    • Về sau có thể có nhiều ứng dụng khác nhau như tự động khám phá công thức, AI ký hiệu, tối ưu hóa biểu diễn toán học

Bài viết liên quan

2 bình luận

 
carnoxen 6 ngày trước

Nếu biểu diễn bằng công thức, thì có vẻ là $eml(x, y) = e^x - ln(x)$ nhỉ

Tuy nhiên, có lẽ nó chỉ thực sự phát huy tác dụng khi xuất hiện bộ xử lý có thể tính $e^x$ hoặc $ln(x)$ trong một lần
 
GN⁺ 8 ngày trước
Ý kiến trên Hacker News

  • Cách tiếp cận này không hẳn là đặc biệt hay có lượng tính toán ít nhất
    Ví dụ, nếu định nghĩa f(x, y) = 1/(x - y) thì nó cũng trở thành một toán tử phổ quát
    Đặt x#y = 1/(x - y), thì x#0 = 1/x cho ta nghịch đảo, và (x#y)#0 = x - y có thể biểu diễn phép trừ
    Việc xây dựng bốn phép toán cơ bản chỉ từ nghịch đảo và phép trừ là một bài toán khá quen thuộc
    Có một chứng minh ngắn liên quan trong ghi chú này

    • Điểm thú vị là cách tiếp cận này còn bao gồm cả các hằng số e, π, i. Nó xử lý được cả phép cộng, phép nhân, lũy thừa, logarit và các hàm siêu việt khác
    • Cách f(x, y) mà bạn nói đến cần giới hạn (limit) để biểu diễn một số khái niệm, còn cách EML thì có cấu trúc cây tính toán để biểu diễn mô hình hệ thống
    • Phát hiện hay đấy. Bài viết có trích dẫn một bài báo năm 1935 (bài PNAS), và thảo luận liên quan cũng tiếp diễn trên MathOverflow
    • Vậy thì tôi tò mò không biết với cách biểu diễn đơn này có suy ra được cả các hàm lượng giác hay không
    • Nhưng với cách này, có vẻ sẽ khó xử lý các hằng số chuẩn hay biểu diễn dạng đóng như e, π, exp, log

  • Thật vui khi thấy một ý tưởng kiểu FRACTRAN xuất hiện trên trang chủ
    Nó làm tôi nhớ đến cách mã hóa stack 1 bit thành số nhị phân.
    Push 0 thì nhân đôi số, push 1 thì nhân đôi rồi cộng 1. pop tương đương với chia cho 2
    Tôi dùng một ngôn ngữ nối chuỗi tên là Rejoice dựa trên các ý tưởng như vậy. Dữ liệu được biểu diễn như các multiset ghép lại bằng phép nhân
    Wiki Rejoice

    • Chẳng phải bạn phải theo dõi kích thước của stack để biết có số 0 ở đầu hay không sao?
    • Nghe như mô tả lại nguyên lý cơ bản của hệ nhị phân theo cách khác thôi

  • Đây là một benchmark tốt để kiểm tra năng lực của LLM

    논문: https://arxiv.org/pdf/2603.21852
"2x + y"를 EML 조합으로 표현하시오

    Opus (trả phí) thất bại vì cho rằng “2” là tuần hoàn, nhưng ChatGPT làm được rồi nên coi như thành công
    ChatGPT (miễn phí) thành công ngay một lần, Grok đoán độ sâu, Gemini thành công, Deepseek không tải được PDF, Kimi dừng giữa chừng, GLM thì ổn

    • Hôm nay tôi mới biết rằng khiêu khích (taunt) LLM thì nó làm tốt hơn. Chắc là có tính cạnh tranh
    • Tôi chỉ sao chép phần tóm tắt vào DeepSeek mà nó vẫn cho ra kết quả. Trừ điểm vì không biết PDF là không công bằng
    • Nếu thích những thử nghiệm kiểu này, tôi khuyên bạn đóng góp cho Terminal Bench Science
    • Tôi đã đổi prompt thành thế này: 
      eml(x,y)=exp(x)−ln(y)
sin(x)/x를 EML과 상수 1로 표현하시오
    • Chế độ instant của meta.ai cũng thành công ngay một lần 
      2x + y = \operatorname{eml}\Big(1,\; \operatorname{eml}\big(\operatorname{eml}(1,\; \operatorname{eml}(\operatorname{eml}(1,\; \operatorname{eml}(\operatorname{eml}(L_2 + L_x, 1), 1) \cdot \operatorname{eml}(y,1)),1)\big),1\big)\Big)
      Gemini lại hiểu nhầm EML là “elementary mathematical layers”

  • Tôi đã trực quan hóa 36 hàm EML hai tầng khác nhau của một biến
    18 hàm đầu cho đầu ra là số thực, còn phần còn lại có giá trị phức ở bước trung gian
    Liên kết ảnh

    • Sẽ thú vị nếu phân loại toàn bộ các hàm cây nhị phân có độ sâu cố định theo kiểu này, rồi mã hóa cây thành số nhị phân
      Các bảng hàm trong sách toán cũ có thể được diễn giải lại như một tra cứu hash đơn giản

  • Câu “có thể thực hiện mọi phép tính chỉ bằng EML và số 1” làm tôi nghĩ đến Iota combinator
    Nó giống với ý tưởng đạt được Turing completeness từ một hệ hình thức tối giản

  • Liên kết bài báo hiện tại là bản v1 nên thiếu hình. Cần đổi sang v2
    Tôi vẫn đang đọc, nhưng nếu đúng thì đây có thể là một phát hiện lớn trong nhiều năm
    Nếu có thể fit dữ liệu hay hàm sóng bằng cây EML thay vì spline hay đa thức,
    thì hàm nhiều biến cũng có thể được học bằng gradient descent rồi chuyển thành cây xấp xỉ EML
    Thậm chí có thể học theo kiểu khớp điều kiện đạo hàm của phương trình Schrödinger
    Nghe hay đến mức đáng nghi, nhưng chuyện kiểu này từng thực sự xảy ra rồi

    • Theo kinh nghiệm tôi nghiên cứu lĩnh vực này suốt 1 năm, EML mạnh nhưng vấn đề là bùng nổ biểu thức
      Chỉ để biểu diễn một phép nhân đã cần cây sâu 8 với hơn 41 lá
      Có một đánh đổi giữa sự thanh lịch của tập phép toán tối thiểu và độ dài biểu diễn
      Tôi đã theo đuổi hướng kết hợp mạng nơ-ron phổ với symbolic regression bằng lý thuyết operad và Category Theory
    • Cũng như lý do người ta không triển khai toàn bộ logic Boolean chỉ bằng NAND: vì hiệu quả tính toán
      Đa thức nhanh hơn xét theo tương quan giữa biểu đạt và chi phí tính toán
    • Bài báo thú vị và thanh lịch, nhưng không phải là phương án cạnh tranh cho hồi quy hay tối ưu hóa
      Điều bạn nói khá giống symbolic regression hiện có. Đây đã là một lĩnh vực trưởng thành
    • Cách dựa trên EML rất ngầu, nhưng ngay cả những hàm đơn giản (ví dụ: +) cũng khó biểu diễn
      Dù vậy đây vẫn là một phát hiện rất thú vị
    • Là một mẹo hay thật, nhưng gọi là phát hiện mang tính trọng đại thì có vẻ hơi cường điệu

  • Có vẻ quá trình suy ra -x bị sai
    Nếu nhìn vào vết thực thi của stack machine, eml(z, eml(x,1)) có dạng e^z - x,
    để nó thành -x thì phải có e^z = 0. Nhưng không tồn tại số phức z như vậy
    Thực ra nếu khai triển z ra thì sẽ gặp vấn đề kiểu ln(0). x^-1 cũng tương tự
    Nếu giả sử ln(0)=∞ và x/∞=0 thì nó sẽ hoạt động theo kiểu “có vẻ hợp lý”

    • Tác giả có nhắc đến ký pháp RPN, nhưng lại chỉ đưa công thức dưới dạng ảnh nên khá bất tiện
      Theo thứ tự tính toán thì sẽ là ln(1)=0 → e-ln(0)=+∞ → e-ln(+∞)=-∞
    • Bài báo cũng thừa nhận vấn đề này. Tôi đã kết luận quá sớm

  • Tôi nảy ra vài ý tưởng thú vị

    1. Nếu thêm trị tuyệt đối dưới dạng sqrt(x*x) thì cũng có thể suy ra min, max, signum
    2. Nếu f(x) và f⁻¹(x) là các hàm song ánh có thể biểu diễn bằng eml(), thì có thể dùng eml(f(x), f(y)) và f⁻¹(1) để tạo ra một nền tảng phổ quát khác
    3. Thay vì logarit tự nhiên, có thể dùng một nền tảng dạng 2^x - log₂(y), và điều này có thể hiệu quả tính toán hơn. Nó gợi nhớ đến Elias omega coding
    4. Nếu có thuật toán tính đạo hàm cho cây eml(), thì có lẽ ta có thể chứng minh rõ ràng hàm nào không thể có nguyên hàm ký hiệu
    5. Việc mở rộng sang miền số phức cũng có thể liên hệ với logic mờ chân trị phức. Có khả năng thống nhất logic Lukasiewicz với logic nhân

  • Hôm qua tôi làm thử dự án emlvm cho vui

  • Phần nói rằng “có thể khôi phục hàm dạng đóng bằng cây EML có độ sâu không quá 4” thực sự rất tuyệt
    Tôi luôn tự hỏi liệu điều đó có khả thi hay không