On Thu, Sep 05, 2019 at 10:46:54AM -0700, Adam Golding wrote: > I want to try automating programming as search where I have various methods > to enumerate the set of all programs in different orders (fastest to halt > first? shortest source code first? etc.) and filter out certain programs > almost like evolutionary programming. I don't have a specific application > in mind really, I wanted to have various enumerators to experiment with, > not unlike the opening of "New Kind of Science", where Wolfram generates > all possible CA programs and then categorizes them according to their > behavior. > > The idea also came up recently in this context: > https://www.facebook.com/adamgolding/posts/10106973704058242 >
I once wrote a program to enumerate typed lambda calculus expressions equivalent to church numerals. It didn't find any interesting ones in feasible time. But machines were slower and more expensive back in the 70's. This was in context of finding the shortest lambda-expression that could represent eash integer, and trying to find the size-restricted lambda-expression that could represent the largest integer. -- hendrik > On Thursday, 5 September 2019 13:17:32 UTC-4, Sage Gerard wrote: > > > > This question can be read a couple of different ways too. What are you > > trying to do once you have the answer you are looking for? > > > > > > > > -------- Original Message -------- > > On Sep 5, 2019, 1:13 PM, Adam Golding < adamg...@gmail.com <javascript:>> > > wrote: > > > > > > What is the shortest program listing the largest list of programs that can > > be listed without looping? > > > > On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote: > >> > >> How about this: a stream of strings which can be be parsed and > >> compiled. (Note that this will loop when it gets to the first program > >> that makes the compiler loop; luckily it's inefficient enough that > >> you'll never actually get there.) > >> > >> #lang racket > >> (define valid-progs > >> (for/stream ([p strings] > >> #:when (valid p)) > >> p)) > >> > >> (define strings > >> (stream-cons "" > >> (for*/stream ([s strings] > >> [i (in-range 0 #x10FFFF)] > >> #:when (not (<= #xD800 i #xDFFF))) > >> (string-append (string (integer->char i)) s)))) > >> > >> (define (valid x) > >> (with-handlers ([exn:fail? (λ _ #f)]) > >> (compile (with-input-from-string x > >> (λ () (begin0 (read) > >> (unless (eof-object? (read)) > >> (error "fail")))))) > >> x)) > >> > >> On Thu, Sep 5, 2019 at 10:58 AM Adam Golding <adamg...@gmail.com> wrote: > >> > > >> > It's okay if the program never halts. > >> > > >> > -- > >> > You received this message because you are subscribed to the Google > >> Groups "Racket Users" group. > >> > To unsubscribe from this group and stop receiving emails from it, send > >> an email to racket...@googlegroups.com. > >> > To view this discussion on the web visit > >> https://groups.google.com/d/msgid/racket-users/70d0b081-eef8-44a6-b2e3-5a72eba7ff5a%40googlegroups.com. > >> > >> > >> > > -- > > You received this message because you are subscribed to the Google Groups > > "Racket Users" group. > > To unsubscribe from this group and stop receiving emails from it, send an > > email to racket...@googlegroups.com <javascript:>. > > To view this discussion on the web visit > > https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com > > > > <https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com?utm_medium=email&utm_source=footer> > > . > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/racket-users/66cee60f-b75c-4c9c-a2b8-a90dfabdfc1e%40googlegroups.com. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20190905213728.6u5voccrebxisalg%40topoi.pooq.com.
