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 > <javascript:>> 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 <javascript:>. > 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.
