Làm thế nào để viết một liệt kê của tất cả các chức năng tính toán?

Question

Động lực: Tôi muốn có thể sử dụng lập trình chức năng đồ chơi bằng các ngôn ngữ không có chức năng đặt hàng đầu tiên, bằng cách sử dụng các số tự nhiên thay vì chức năng.

Chức năng phổ quát là hàm f: N -> (N -> N), tương đương f: N * N -> N liệt kê tất cả các hàm có thể tính toán. Nói cách khác, có một số k sao cho f (k) là hàm bình phương, có một số j sao cho f (j) là hàm nguyên tố thứ n, v.v.

Để viết một hàm như vậy, ta có thể lấy bất kỳ ngôn ngữ Turing-hoàn thành (trình biên dịch ngôn ngữ lập trình, lambda calculus, Turing máy ...) và liệt kê tất cả các chương trình. Tôi muốn cho phép không chỉ đánh giá, mà còn cho phép hoạt động trên các chức năng như bổ sung, thành phần, currying. Ví dụ, cho các chỉ số của hai hàm f, g tôi muốn biết chỉ số của hàm f + g, hoặc f được tạo thành với g là gì. Điều này sẽ cho phép "lập trình đồ chơi chức năng".

Cách tốt để viết thư viện mã như vậy là gì? Tôi không tìm kiếm một tarpit Turing tối giản mà sẽ đấu tranh để tính giai thừa 10, cũng không phải tôi không muốn viết một trình biên dịch nâng cao. Nó cần phải có một số chức năng cơ bản như bổ sung và khả năng để viết vòng lặp, nhưng không nhiều hơn nữa.

Giải pháp ở tất cả các ngôn ngữ cấp cao đều được chào đón. Pseudocode, Haskell và Python được ưu tiên. Bạn có thể giả định số học chính xác tùy ý. Sử dụng eval hoặc tương tự không được phép.

Làm rõ: Các hàm được liệt kê sẽ bao gồm tất cả các hàm partial recursive (computable) - bao gồm các hàm không dừng trên một số yếu tố đầu vào. Chức năng phổ quát sẽ treo trong trường hợp đó; tất nhiên điều này là không thể tránh khỏi. Xem thêm: các hàm đệ quy m - http://en.wikipedia.org/wiki/Μ-recursive_function.

Answer 1

không phải là một câu hỏi dễ dàng. Tôi đoán bạn phải bắt đầu với một máy phát điện chức năng mà có thể tạo ra tất cả các chức năng một. Điều này sẽ dẫn đến một điều tra.

Vì bạn phải đối phó với nhiều thứ nguyên vô tận ... hãy suy nghĩ về nó.

Hãy giảm vấn đề về chức năng với các tham số n và các thao tác cơ bản +, -, *, /.
Hãy xây dựng tất cả các chức năng chỉ với một thao tác:

một + một
a + b
một - một
a - b
một * a
a * b
một/một
a/b

Tôi đoán rất dễ thấy rằng một số hàm này có ý nghĩa hơn vì những hàm khác và một số hàm có thể bằng nhau, nhưng ít nhất, đó là ánh xạ có thể tạo thô một vòng lặp.

Bây giờ trong phiên bản kế tiếp, người ta có thể dễ dàng thêm vào mỗi một trong các chức năng

• một trong những thông số đã tồn tại với tất cả các hoạt động
• một tham số thứ ba với tất cả các hoạt động

Sau đó bạn có một danh sách rất lớn các chức năng mà bạn có thể lặp lại bước hai.

Vì hàm là một hàm ước tính tất cả các hàm phức tạp hơn như sin và log (chuỗi taylor), nên chúng cũng được đề cập trong không gian chức năng này.

Điều này có hữu ích không? Vui lòng chỉnh sửa bài đăng này!

Chỉ cần đọc lại bài đăng của bạn. Nếu bạn muốn liệt kê tất cả các hàm có lập trình và không chỉ số một lần, tôi đoán nó sẽ phức tạp hơn. Tôi đoán sau đó nó sẽ có ý nghĩa để làm việc với một bản đồ "chức năng < -> số" bằng cách nén nguồn của chức năng của bạn và điều trị các tập tin zip như một số lượng lớn. Cách khác xung quanh, bạn có thể thử giải nén bất kỳ số nào và xem nó có tạo ra một hàm hữu dụng hay không :-) Nhưng tôi đoán bạn sẽ có rất nhiều số không phải là tệp zip.

Nhưng nó sẽ thỏa mãn yêu cầu của bạn rằng đối với mọi chức năng có một số đại diện cho nó :-)

Answer 2

Điều bạn muốn được gọi là thông dịch viên.

Trước tiên, bất kỳ điều tra nào với các thuộc tính bạn muốn sẽ không phù hợp với các chức năng thú vị mà bạn muốn thao tác trong 2^32 đầu tiên hoặc thậm chí 2^64 đầu tiên, số nguyên. Vì vậy, bạn sẽ cần số nguyên lớn hơn, phân bổ một nơi nào đó trong bộ nhớ và tham chiếu thông qua một con trỏ.

Tại sao không sử dụng mảng ký tự (chuỗi) biểu diễn chương trình theo bất kỳ cú pháp hiện tại nào? Hãy xem xét một chuỗi như một số nguyên nếu điều đó làm cho bạn hạnh phúc. Số lượng hàm để tính f1()+f2() là chuỗi được tạo thành (đại diện của f1), "+" và (đại diện của f2). Bạn có ý tưởng ...

Cách tiếp cận này không có gì là không có sự biểu hiện của một hàm, điều đó có thể ngụ ý trong câu hỏi của bạn (tôi không chắc chắn). Điều tôi chắc chắn là tính đơn nhất của biểu diễn không tương thích với việc có các hoạt động thành phần đơn giản hoặc thậm chí tính toán được trên các biểu diễn hàm - Ví dụ, sẽ có một giải pháp dễ dàng cho vấn đề Halting nếu nó không phải như vậy.

Answer 3

Bạn có thể sử dụng bất kỳ ngôn ngữ lập trình nào để bạn có thể xác định xem một chương trình nào đó có phải là chương trình hay không và liệt kê tất cả các chương trình theo thứ tự từ điển. Để tránh ít nhất một chút của vụ nổ tổ hợp, bạn có thể gán các tên do người dùng định nghĩa (các biến, hàm, v.v.) theo dạng chuẩn hóa. Rõ ràng, điều này sẽ dẫn đến một số lượng lớn các chức năng, và nó sẽ không dễ dàng để chọn ra cái nào thực sự hữu ích. Bất kỳ phương pháp cắt tỉa tự động nào cũng sẽ loại trừ một số chức năng mà bạn thực sự muốn, hoặc không cắt vụ nổ tổ hợp đủ hữu ích hoặc cả hai.

Những bất lợi khác của việc này là rất khó để chuyển từ số sang hàm: khó tìm ra cách tốt hơn để tìm hàm 433,457,175,432,167,463 hơn để liệt kê khoảng bốn trăm nghìn nghìn hàm.

Cách khác là mã hóa một hàm thành một số bằng cách ánh xạ các biểu tượng đến các số và kết hợp chúng một cách hiệu quả.

Giả sử rằng các ký hiệu là +, -,: =, ==, <, nếu, sau đó, endif, do, end_do_condition, enddo và dấu phân tách câu lệnh. Đó là 11 biểu tượng ngay tại đó, không có biến, cho một bộ khá nhỏ mà không bao gồm bất cứ điều gì giống như một cuộc gọi chức năng, và yêu cầu bạn nhân và chia mình. (Tôi không thực sự chắc chắn điều này sẽ làm việc mà không có một nhà điều hành hợp lý hoặc hai.) Thêm năm tên biến, và bạn đã có một ngôn ngữ lập trình với các ký tự 4-bit. Điều này có nghĩa là tối đa mười sáu ký tự sẽ khớp với số nguyên không dấu 64 bit.Một khi bạn đã có điều này, tất cả các mối quan hệ có thể có giữa các hàm sẽ được biểu diễn như một mối quan hệ số học, nhưng một mối quan hệ vô cùng phức tạp sẽ phức tạp đến mức cần thực hiện ngay trong thực tế.

Tóm lại, trong khi điều này về mặt lý thuyết có thể, nó sẽ là quá vụng về trong thực tế. Nó có thể sẽ dễ dàng hơn để viết một thông dịch viên cho một ngôn ngữ chức năng trong ngôn ngữ phi chức năng của bạn lựa chọn.

Answer 4

Để viết một chức năng như vậy, ai có thể lấy bất kỳ ngôn ngữ (lập trình biên dịch ngôn ngữ, lambda calculus , máy Turing ...) và liệt kê tất cả các chương trình Turing hoàn tất

tôi m không chắc chắn nếu điều đó có thể được thực hiện ở tất cả ... Nó cảm thấy như nó đi ngược lại luận án Turing-Giáo Hội. Để liệt kê tất cả các chương trình, trước tiên bạn cần một thuật toán xác định chương trình nào hợp lệ và chương trình nào không, và điều đó là không thể ... Trừ khi bạn không quan tâm đến điều đó và cho phép các chương trình không chính xác trong ngôn ngữ của bạn.

Nhưng có lẽ Godelization của một hệ thống chính thức có thể giúp bạn ... Tôi sẽ thử với Lisp, có mã như dữ liệu có thể giúp ích rất nhiều.

Answer 5

Không chắc tôi hiểu. Một điều mặc dù - bạn không thể liệt kê tất cả các chức năng có thể tính toán. Câu trả lời ngắn gọn: bởi vì nếu không sẽ có một phần mềm chống virus phổ quát. Câu trả lời dài: bởi vì nếu có một điều tra như vậy, bạn sẽ có trong bộ đó cũng là hàm tự tính toán liệt kê. Giống như nghịch lý của Russel.

Một câu trả lời khác cho câu hỏi của bạn sẽ là - bạn muốn `` liệt kê '' tất cả các chức năng có thể tính toán; để làm điều đó, bạn có thể muốn biểu diễn chúng dưới dạng số nguyên tố và sử dụng thành phần của chúng làm phép nhân. Điều này sẽ đảm bảo tính duy nhất. Factorisation sẽ cung cấp cho bạn chức năng đảo ngược.

Answer 6

Trong khi nó không phải là quá khó để liệt kê tất cả có thể biểu trong một số ngôn ngữ, bạn sẽ không thể để hạn chế những đối với những biểu thức biểu thị chức năng chấm dứt. Nhưng nếu bạn không quan tâm đến việc chấm dứt, sử dụng các bộ phối hợp (với một số nguyên tố số học được ném vào để có ích) có thể là cách tốt nhất, vì bạn tránh giới thiệu các tên biến theo cách đó.

Answer 7

Như Pascal đã nói, những gì bạn muốn là một thông dịch viên, nhưng người ta có thể làm tốt hơn nữa: Sử dụng bộ xử lý làm thông dịch viên trực tiếp.

Nạp số N (chẳng hạn như một mảng lớn int) trực tiếp vào bộ đệm và thực hiện bộ đệm này dưới dạng mã machinecode.

Đối với mọi chức năng có thể, máy tính của bạn có thể thực thi có tồn tại N. Không may. không phải mọi N là một chương trình hợp lệ (điều này không được yêu cầu) hoặc chương trình chấm dứt (điều này là không thể). Mặt khác, chức năng này sẽ tạo ra những viên đá quý như World of Warcraft, Microsoft Office 17 bao gồm Service Pack 6 và Windows 9.