Adam, I strongly recommend you take a look at Levin Search (aka Universal Search), which enumerates and runs programs by dovetailing in a smart way: http://people.idsia.ch/~juergen/mljssalevin/node4.html http://www.scholarpedia.org/article/Universal_search#Universal_search
This avoids the halting problem including the running time in the complexity: If a program q solves the problem in time Tq, then Levin Search solves the problem in time Tq / wq, where wq = 2^-l(q) with l(q) being the size in bits of program q. In other words, Levin Search solves all search problems at least as fast as the fastest program within a constant factor that depends on the inverse of the prior of the program. IMO, Levin Search is one of the most important algorithms ever. On Thu, Sep 5, 2019 at 7:13 PM Sage Gerard <s...@sagegerard.com> wrote: > In all honesty, I think you are asking for something so broad that it > would be more practical if you ran experiments and simulations against the > specific space you are curious about. Once you do that enough times you'll > be able to pick out the patterns. I'm not convinced there is an off-shelf > design for what you want without a patent attached to it. > > *~slg* > > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Thursday, September 5, 2019 2:09 PM, Sage Gerard <s...@sagegerard.com> > wrote: > > It almost sounds like you want a cleaner interface for defining a neural > net. > > *~slg* > > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Thursday, September 5, 2019 2:07 PM, Adam Golding < > adamgold...@gmail.com> wrote: > > At this point I don't need the search (through the space of all programs) > to be efficient I just need it to be 'total' in that every program would be > reached given a countable infinity of time. Then I could alter this search > to search the same space in a different order (still total) and compare > empirically which is 'more efficient' (depends what programs you're > searching for). For example, enumerating possible racket programs from > shortest to longest source would be one order, and enumerating them from > shortest to longest runtime would be another... > > On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote: > >> Thanks, that helps. >> >> In the way I read this, it sounds like you want a program that computes >> the most efficient search algorithm regardless of the context in which said >> algorithm is used. >> >> Is that accurate? >> >> *~slg* >> >> >> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ >> On Thursday, September 5, 2019 1:48 PM, Adam Golding <adamg...@gmail.com> >> wrote: >> >> Basically I want to enumerate programs with as few assumptions as >> possible aka enumerate the largest set of programs I can--I want to be able >> to enumerate them in a variety of different orders to compare search >> strategies. >> >> On Thursday, 5 September 2019 13:46:54 UTC-4, 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 >>> >>> 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> 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. >>>> 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...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%40googlegroups.com >> <https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%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/1be52cfa-9dc0-4379-b1fa-dfe65df2b2e9%40googlegroups.com > <https://groups.google.com/d/msgid/racket-users/1be52cfa-9dc0-4379-b1fa-dfe65df2b2e9%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/-2Hzy33bIrMUcvTgQ0IngN1Zo4YWWbuOVrIgN6LvIPMlw2LihHG7ZljvZKAtrR9TIacZ-kbusZT5IxHeb3neYX1UCCulNlcLT9ccSivVkNQ%3D%40sagegerard.com > <https://groups.google.com/d/msgid/racket-users/-2Hzy33bIrMUcvTgQ0IngN1Zo4YWWbuOVrIgN6LvIPMlw2LihHG7ZljvZKAtrR9TIacZ-kbusZT5IxHeb3neYX1UCCulNlcLT9ccSivVkNQ%3D%40sagegerard.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/CABNTSaHcGsTc2gnJMW6Zh1%2BFoK4fV%3DmM%2Bv7e7MebFbK5XX8SsA%40mail.gmail.com.
