Có các chương trình lặp lại các chương trình mới không?

Question

Trong khoảng một năm, tôi đã suy nghĩ về cách viết chương trình viết chương trình. Điều này chủ yếu sẽ là một bài tập vui tươi mà có thể dạy cho tôi một số khái niệm mới. Nguồn cảm hứng của tôi đến từ negentropy và khả năng để xuất hiện từ hỗn loạn và hỗn loạn mới phát sinh trong trật tự trong kế tiếp vô hạn.

Để cụ thể hơn, chương trình sẽ bắt đầu bằng cách viết một chuỗi ngẫu nhiên ngắn. Nếu chuỗi biên dịch chương trình sẽ ghi lại nó để so sánh sau này. Nếu chuỗi không biên dịch chương trình sẽ cố gắng viết lại nó cho đến khi nó biên dịch. Như nhiều chuỗi (mini 'vô dụng' chương trình) được đăng nhập, họ có thể được phân tích cú pháp cho tương đồng và được sử dụng để tạo ra một ngữ pháp. Ngữ pháp này sau đó có thể được rút ra để viết nhiều chuỗi hơn có khả năng biên dịch cao hơn các chuỗi hoàn toàn ngẫu nhiên.

Điều này rõ ràng hơn một chút ngớ ngẩn, nhưng tôi nghĩ sẽ rất thú vị khi thử và phát triển một chương trình như thế này. Và như một sản phẩm phụ tôi nhận được một loạt các chương trình độc đáo mà tôi có thể hình dung và gọi nghệ thuật.

Tôi có thể sẽ viết điều này trong Ruby do cú pháp đơn giản và biên dịch động của nó và sau đó tôi sẽ hình dung trong quá trình xử lý bằng cách xử lý ruby.

Những gì tôi muốn biết là:

• Có một tên cho loại hình này của chương trình?
• Điều gì hiện có trong trường này?
• Ai là người đóng góp chính?
• THƯỞNG! - Theo cách nào tôi có thể gán giá trị cho các chương trình đầu ra ngoài biên dịch (y/n)?
  Tôi có thể muốn mở rộng chức năng của chương trình này để tạo ra một chương trình dựa trên các tham số, nhưng tôi muốn chương trình xác định các tham số đó thông qua việc chạy các chương trình biên dịch và gán ý nghĩa cho đầu ra của chương trình. Câu hỏi này có lẽ liên quan nhiều hơn hợp lý để nhận tiền thưởng, nhưng nếu bạn có thể nghĩ ra một cách đơn giản để thực hiện một việc như thế này dưới 23 dòng hoặc một siêu liên kết, hãy ném nó vào câu trả lời của bạn.

Tôi biết rằng đây không phải là lập trình meta và từ ít tôi biết về AI và thuật toán sinh sản, chúng thường hướng tới mục tiêu nhiều hơn những gì tôi đang nghĩ. Điều sẽ tối ưu là một chương trình liên tục viết lại và cải thiện chính nó vì vậy tôi không phải^_^

Answer 1

Tra cứu "lập trình di truyền".

Chỉnh sửa để trả lời nhận xét:

@chris, @Kasturi: true. Điều được mô tả trong OP là một hệ thống để suy luận ngữ pháp bằng các nỗ lực brute-force để thực hiện một số cú pháp biên dịch cụ thể, và sau đó tạo lại cú pháp cụ thể mới từ ngữ pháp. Nếu bạn đang bị ràng buộc để có một cái gì đó rất phù hợp với mô tả đó ... lời khuyên tốt nhất tôi có là nhìn vào xây dựng một mô hình Markov ẩn từ cú pháp cụ thể trong một số ngôn ngữ với cú pháp rất tối thiểu. Tôi muốn xem xét sử dụng một logic tổ hợp tối thiểu (một cái gì đó tương tự như trong ngôn ngữ Unlambda).

Mặt khác, lập trình di truyền là một kỹ thuật với một số thực hành phát triển và văn học, và không phải là "xác định" mà là một quá trình ngẫu nhiên. Nó cũng là một thuật ngữ khá rộng - được cho là hệ thống của OP là một trường hợp giới hạn của GP với 0% crossover và 100% đột biến.

Answer 2

Một dự án khác mà bạn có thể làm là làm việc trên thứ gì đó đột biến khi không vượt qua bài kiểm tra đơn vị nhất định để vượt qua bài kiểm tra đơn vị.

Ví dụ, với một thực hiện

def add(a,b) 
    a 
end 

Bạn có thể thêm một thử nghiệm

assert_equal 3, Foo.new.add(1,2) 

và yêu cầu chương trình của bạn để thử bất kỳ sự kết hợp của các phương pháp trên a trong add (ví dụ, a.-(b), a.to_s , a.+(b)) cho đến khi một trong các đột biến vượt qua bài kiểm tra đó và các bài kiểm tra hiện có.

Bạn có thể muốn xem xét heckle (hoặc Zentest?) Để biết ví dụ về việc thay đổi mã đang được thử nghiệm.

Answer 3

Bạn đã nghe nói về nanopond chưa? Khái niệm này tương tự như khái niệm của bạn. Mỗi pixel được đưa ra một chuỗi được tạo ngẫu nhiên được chạy thông qua trình biên dịch. Thông thường, điều này không tạo ra bất kỳ chương trình hợp lệ nào. Tuy nhiên, mỗi một lần trong một thời gian, một chuỗi được tạo ngẫu nhiên bằng cách nào đó sẽ được định dạng hoàn toàn để có thể tự tái tạo thành một pixel lân cận. Chẳng mấy chốc, nó trở thành một trận chiến mà chương trình có thể tái tạo tốt hơn cái kia.

Điều bạn đang nói đến là thuật toán di truyền, vâng, nhưng tối đa hóa một điều và một điều duy nhất: Khả năng tái tạo.

Đây là nguồn gốc thiết yếu cho tất cả hiện tượng tự nhiên không phổ biến: một thực thể phức tạp được tạo ngẫu nhiên có khả năng tái tạo.

Thuật toán di truyền cổ điển áp đặt tiêu chí sinh sản nhân tạo - chương trình thực hiện công việc tốt nhất là nhân tạo được chọn để tạo lại.

Điều bạn ngụ ý là một loại tính toán lựa chọn tự nhiên. Tức là, các chương trình sẽ phát triển dựa trên khả năng của chúng để tự làm tái sản xuất và không có gì khác.

Điều này có tạo ra điều gì đó hữu ích không? Có lẽ không. Trừ khi bạn, có thể, đã cho các chương trình của bạn truy cập vào internet hoặc một số API bên ngoài khác mà họ có thể truy cập ngẫu nhiên và có thể lan truyền qua internet.

Thật không may, hệ thống được mô tả của bạn vẫn có một số tiêu chí sinh sản nhân tạo: khả năng biên dịch.

Vì khả năng biên dịch = khả năng tái tạo, bạn đã thiết lập một cách giả tạo các chương trình của mình để phát triển theo hướng biên dịch.

Biên dịch cái gì? Nó không quan trọng, bởi vì bất kỳ chương trình nào biên dịch đều có khả năng tái tạo như là chương trình cuối cùng. Giả sử bạn bằng cách nào đó đã tạo ra một chương trình có thể xuất ra dãy Fibonacci. Hoặc một chương trình có thể đánh bại một tướng cờ vua. Mát mẻ! Thật không may, nó sẽ được sao chép? Nó có đặc biệt không?

Không hề; nó muốn được coi là "phù hợp" cho sinh sản như các chương trình print('k')

Tôi đề nghị có lẽ điều hành một khuôn khổ một cách ngẫu nhiên chạy chuỗi các chương trình có thể truy cập của API mà có thể:

• đọc/ghi vào ổ đĩa cứng, và tất cả của một đột ngột, bạn có các chương trình có thể viết chuỗi ngẫu nhiên như các chương trình, bản thân.
• Xóa/sửa đổi các tệp khác trên ổ đĩa cứng; điều này cho phép các chương trình có thể cạnh tranh với nhau. API của bạn có thể được thiết kế sao cho một tệp chỉ có thể bị xóa nếu "độ mạnh" (giá trị tùy ý ... có lẽ độ dài ký tự) của chương trình mạnh hơn tệp.
• Chạy các tập lệnh khác trên ổ cứng ... có lẽ cả các tập lệnh khác mà chúng tự viết
• Truy cập internet; đến một máy chủ web? Khả năng viết/đính kèm/gửi/đọc e-mail?

Tôi nghĩ rằng một chương trình viết chương trình có thể tự tái sản xuất có thể tạo ra kết quả tốt hơn chương trình viết chương trình có thể biên dịch.

Trừ khi bạn chỉ muốn thứ hai; sau đó có thể bạn có thể tối đa hóa độ dài chương trình. Nhưng khả năng có điều gì đó thú vị xảy ra? Không nhiều; bất kỳ chương trình nào "biên dịch" với độ dài nhất định sẽ chỉ giống như "tái tạo".

Answer 4

Điều gì sẽ là tối ưu là một chương trình mà liên tục viết lại và cải thiện bản thân nên tôi không cần phải

làm các bước sau:

1. Viết bộ tạo số giả ngẫu nhiên trong hội,, tổ hợp. (chế độ thực)
2. Sửa đổi chương trình để ghi ra (ví dụ) 64k số ngẫu nhiên và thực hiện FAR JMP tới byte đầu tiên.
3. (tùy chọn) Tạo trình điều khiển cho bộ đếm giờ đồng hồ của chó để ngăn vòng lặp vô hạn
4. Tải lên bộ khởi động của một số thiết bị.
5. Tải nhiều máy tính. Cấu hình để nếu chúng có lỗi gấp ba lần, chúng sẽ khởi động lại và khởi động từ bộ khởi động của thiết bị
6. Khởi động máy tính và chờ vài thập kỷ (hoặc hàng thế kỷ) để sản xuất một cái gì đó hữu ích
7. Lợi nhuận!

Answer 5

Tìm kiếm Grammatical Evolution.

Answer 6

Tác phẩm đầu nhưng rất thú vị dọc theo các dòng này là "AM" của Doug Lenat (Nhà toán học) và Eurisko (tổng quát về AM).

Eurisko đã phát triển một tập hợp các thông số kỹ thuật bằng cách kiểm tra cách các điều kiện biên ảnh hưởng đến việc giải quyết vấn đề. Nó không tạo ra rác hơn là thử nó, thay vào đó, nó lấy một phương pháp giải quyết vấn đề yếu và tìm thấy các trường hợp mà nó có thể là một công việc tốt hơn nhiều, và tạo ra một phiên bản vá của trình giải quyết vấn đề.