# God's Own Algorithms.

## John Carter — 2002-04-03 00:46:44

    Up to now, I have been rather reluctant to accept recursion via combinator

    as anything but an academic curiosity. But the idea of GOA's (God's Own

    Algorithm's) suddenly makes me very interested in them indeed. Especially

    in the light of the thread on minimal bases.

    Given any program one can always concieve of it implemented by a GOA. ie.

    The shortest program that does exactly the same thing.

    Now there are two features about Joy that make this concept very

    interesting.

    One is the "recursion" free nature. Traditionally one of the ways of

    hunting a GOA is to break everything into smaller and smaller subroutines

    which call each other in fantastical ways. Now in recursion free Joy a

    "word" can always be replaced by its definition without it ever appearing

    recursively in the expansion.

    Now add in the idea of a minimal base, then any Joy program can be

    expanded to a single string involving nothing but the minimal base

    operators.

    Thus we have a remarkably clean concept for a GOA. That program

    that provably behaves the same as the defining program, yet is the

    shortest string when expanded all the way down to the chosen minimal base.

    Thus a GOA is defined by the defining program and the chosen minimal base.

    It would be interesting to create a program that, given a program and a

    base, searches for the GOA.

    It would then be very interesting to study the GOA's and look for nifty

    idioms.

    This also allows to define the concept of power of a base.

    Given a set of defining programs, the most powerful base is that for which

    the corresponding GOA's, in some sense eg. minimax, average,... are the

    shortest.

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Zeitgeist shutting down for corrective maintenance, please log off.

## Manfred von Thun — 2002-04-03 09:43:07

    On Wed, 3 Apr 2002, John Carter wrote:

     > Up to now, I have been rather reluctant to accept recursion via combinator

    > as anything but an academic curiosity.

     The idea was to capture the most common recursion patterns in a few

    combinators. It works well for linear and binary recursion, and for

    folding (and hence concatenating, filtering and mapping) lists.

    Many programming languages do the same. In Joy one has the additional

    advantage that static typing does not get in the way, and no fancy

    moves are needed to circumvent it.

    But recursion can express the weirdest recursion patterns, and I doubt

    whether there are any nice _clean_ combinators that capture all patterns.

    Of course there is the y combinator, and any of its cousins. They can

    express any recursion pattern, but the resulting programs can look

    rather ugly. (Just try to rewrite the Lisp interpreter with its

    eval and apply - but do not use recursion.)

     > But the idea of GOA's (God's Own

    > Algorithm's) suddenly makes me very interested in them indeed. Especially

    > in the light of the thread on minimal bases.

    >

    > Given any program one can always concieve of it implemented by a GOA. ie.

    > The shortest program that does exactly the same thing.

           ^^^^^^^^

    If "shortest" means "shorter than all others", then there may not be

    such a program because two or more may have the same length.

    If "shortest" means "no longer than any others", then there may be

    such a program, and possibly several others.

    BUT: there will not be an algorithm for finding it.

    This is a consequence of an interesting theorem in

    computability theory. Whereas just about all other bad-news

    theorems (Halting, Undecidability, Imcompleteness) are based on

    diagonalisation and hence indirectly on the ol' Liar paradox,

    this theorem is based - of all things - on Berry's paradox:

    Let k be "the least positive integer which is not denoted by any

    expression in the English language containing fewer a hundred words".

    (There cannot be such an integer, because if there were some such k,

    then the quoted expression does denote it after all.)

    In

       Machtey, M. and Young, P.,

       _An Introduction to the General Theory of Algorithms_

       Elsevier North Holland 1979

    you will find on pp 5-7 a surprisingly simple proof of the impossibility

    of a certain optimisation problem: For any integer n, find a shortest

    (in the second sense) program that prints that integer. There is no

    program that can do that. (Of course, for any candidate program one

    can prove that indeed it is the shortest - but that is a different

    matter.)

    If I remember correctly, the theorem can be extended to similar

    optimisation problems, including finding shortest programs to do anything.

    I hope this will stop somebody from trying to find what cannot be found

    because it does not exist.

     > Now there are two features about Joy that make this concept very

    > interesting.

    >

    > One is the "recursion" free nature. Traditionally one of the ways of

    > hunting a GOA is to break everything into smaller and smaller subroutines

    > which call each other in fantastical ways. Now in recursion free Joy a

    > "word" can always be replaced by its definition without it ever appearing

    > recursively in the expansion.

    >

    > Now add in the idea of a minimal base, then any Joy program can be

    > expanded to a single string involving nothing but the minimal base

    > operators.

    >

    > Thus we have a remarkably clean concept for a GOA. That program

    > that provably behaves the same as the defining program, yet is the

    > shortest string when expanded all the way down to the chosen minimal base.

    >

    > Thus a GOA is defined by the defining program and the chosen minimal base.

    >

    > It would be interesting to create a program that, given a program and a

    > base, searches for the GOA.

     Impossible, by the above. But one might well be satisfied with what

    one knows to be second-best - just a reasonably short one would do.

    At the same time, even finding a reasonably short one may well be

    computationally unfeasible.

     > It would then be very interesting to study the GOA's and look for nifty

    > idioms.

    >

    > This also allows to define the concept of power of a base.

    >

    > Given a set of defining programs, the most powerful base is that for which

    > the corresponding GOA's, in some sense eg. minimax, average,... are the

    > shortest.

     Yes, that is a useful notion. But do keep in mind that all sorts of

    very mature optimising compilers (for other languages) exist which

    only aim for what is third-best  - and know that even second-best

    takes just far too long to find.

    I hope this is of some help.

      - Manfred

## John Carter — 2002-04-04 05:30:05

    On Wed, 3 Apr 2002, Manfred von Thun wrote:

     > > But the idea of GOA's (God's Own

    > > Algorithm's) suddenly makes me very interested in them indeed. Especially

    > > in the light of the thread on minimal bases.

    > >

    > > Given any program one can always concieve of it implemented by a GOA. ie.

    > > The shortest program that does exactly the same thing.

    >       ^^^^^^^^

    > If "shortest" means "shorter than all others", then there may not be

    > such a program because two or more may have the same length.

    > If "shortest" means "no longer than any others", then there may be

    > such a program, and possibly several others.

     True, GOA's would not necessarily be unique. One could have a

    mini-pantheon of GOA's, but the length of the GOA's would be

    unique for any program.

     > BUT: there will not be an algorithm for finding it.

    > This is a consequence of an interesting theorem in

    > computability theory. Whereas just about all other bad-news

    > theorems (Halting, Undecidability, Imcompleteness) are based on

    > diagonalisation and hence indirectly on the ol' Liar paradox,

     Last night I was contemplating this and I saw that I would hit up against

    the "bad-news" in general. But that need not cause alarm and despondency,

    in that non-halting programs with an infinite input range are not very

    practical anyway. I curious to know what techniques could I learn from

    GOA's for practical programs.

    So if we constrain the set of programs we deal with to those, which given

    a finite N, halt on all inputs within N steps.

    A fierce constraint, especially if N is smallish, but enough to include a

    fair number of nifty practical programming idioms.

     > of a certain optimisation problem: For any integer n, find a shortest

    > (in the second sense) program that prints that integer. There is no

    > program that can do that.

     It's the _any_ that is not relevant here. There are two inputs to the

    GOA(p,b) function. b the base and p the program. I'm quite sure that

    GOA(p,b) is non-computable in general. However for a small but perhaps

    useful and interesting subset of programs, it is.

    Whilst I would love to feed the 150000 line C++ and Java monster I'm

    working on into the GOA function, I would be content with merely

    uncovering more expressive one or two line idioms.

     > > This also allows to define the concept of power of a base.

    > >

    > > Given a set of defining programs, the most powerful base is that for which

    > > the corresponding GOA's, in some sense eg. minimax, average,... are the

    > > shortest.

    >

    > Yes, that is a useful notion. But do keep in mind that all sorts of

    > very mature optimising compilers (for other languages) exist which

    > only aim for what is third-best  - and know that even second-best

    > takes just far too long to find.

     Ah, but what do optimising compilers compile into. Machine instructions.

    There are two views of machine instructions - CISC and RISC.

    CISC means have lots of powerful instructions.

    RISC means have a few instructions you really need and make them fast.

    A powerful base would be the best of both worlds.

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Zeitgeist shutting down for corrective maintenance, please log off.

## Brent L Kerby — 2002-04-04 06:25:56

    > [impossibility of finding the shortest program that does a certain thing]

     It's interesting that this problem is said to be impossible to solve, whereas my

    brute-force searcher is an apparent solution. Of course, the theorem is correct,

    and the problem is truely impossible.

    It's just that the brute-force searcher is not a true solution in all cases,

    although it works well for very small program lengths (actually, only for

    ridiculuously small program lengths, because of the inefficiency of my

    algorithm, sadly). The thing that makes the problem impossible, even by

    brute-force search (starting with the smallest programs and working upward) is

    that in the course of the brute search, we are bound to try a non-terminating

    program, on which we will get stuck forever. In my searcher, I use a heuristic

    that if a program takes more than 100 steps and has not terminated, then it is

    probably non-terminating, and so the searcher moves on to the next candidate

    program. Of course, with larger programs, which can take a long time to

    terminate, but nonetheless still terminate (and possibly even giving the desired

    result in the shortest possible way), this heuristic would be useless; the

    problem is that it is impossible, in general, to tell if a program is

    non-terminating, except by trying it out and running it, in which case if it is

    non-terminating, we'll never know for sure until the end of eternity.

    However, although we can't in general find the _shortest_ program, it is

    possible, theoretically at least, to find the _fastest_ program, by brute-force

    search, at least in the context of Joy combinators (but, since a Joy

    combinator-reduction machine is Turing-complete, this generalizes, really). The

    reason is that we can use a basic abstraction algorithm on our desired program

    (using i, cons, dip,  sip, and zap), which will give a worst-case scenario for

    how long a program will take. For example, say we wanted to find a fast way of

    doing bury2:

      [C] [B] [A] bury2 == [A] [C] [B]

    we could find a worst-case by using an abstraction algorithm:

       A\ B\ C\ [A] [C] [B]

    == A\ B\ [[A]] dip [B]

    == A\ [[[A]] dip] dip

    == [A\ [[A]] dip] cons dip

    == [[A\ [A]] cons dip] cons dip

    == [[] cons dip] cons dip

    And then, and we try this program out and count how many steps it takes:

       [C] [B] [A] [[] cons dip] cons dip

    == [C] [B] [[A] [] cons dip] dip

    == [C] [A] [] cons dip [B]

    == [C] [[A]] dip [B]

    == [A] [C] [B]

    Depending on the exact way in which steps are counted, you might this consider

    this to take 7 steps. Then, because of this, we don't have to waste any more

    than 7 steps on a non-terminating program, because after that we know it could

    not be the fastest, even if it did eventually terminate. Also, our search will

    be over once we finish programs larger than size 7, because all programs bigger

    than that will take longer than 7 steps to finish (at least in a certain

    formalization of "steps"), assuming each word is executed at least once (and, if

    some words are unused, then that program obviously could not be the fastest).

    Of course, that's all just theoretical. Really, a brute-force search is totally

    impractial for large programs, due to the exponential slowness (perhaps this

    could change someday though, with quantum computing, but if I understand right,

    even quantum computing cannot solve an exponential problem in linear time).

    - Brent

## Brent L Kerby — 2002-04-04 06:29:22

    > [impossibility of finding the shortest program that does a certain thing]

     It's interesting that this problem is said to be impossible to solve, whereas my

    brute-force searcher is an apparent solution. Of course, the theorem is correct,

    and the problem is truely impossible.

    It's just that the brute-force searcher is not a true solution in all cases,

    although it works well for very small program lengths (actually, only for

    ridiculuously small program lengths, because of the inefficiency of my

    algorithm, sadly). The thing that makes the problem impossible, even by

    brute-force search (starting with the smallest programs and working upward) is

    that in the course of the brute search, we are bound to try a non-terminating

    program, on which we will get stuck forever. In my searcher, I use a heuristic

    that if a program takes more than 100 steps and has not terminated, then it is

    probably non-terminating, and so the searcher moves on to the next candidate

    program. Of course, with larger programs, which can take a long time to

    terminate, but nonetheless still terminate (and possibly even giving the desired

    result in the shortest possible way), this heuristic would be useless; the

    problem is that it is impossible, in general, to tell if a program is

    non-terminating, except by trying it out and running it, in which case if it is

    non-terminating, we'll never know for sure until the end of eternity.

    However, although we can't in general find the _shortest_ program, it is

    possible, theoretically at least, to find the _fastest_ program, by brute-force

    search, at least in the context of Joy combinators (but, since a Joy

    combinator-reduction machine is Turing-complete, this generalizes, really). The

    reason is that we can use a basic abstraction algorithm on our desired program

    (using i, cons, dip,  sip, and zap), which will give a worst-case scenario for

    how long a program will take. For example, say we wanted to find a fast way of

    doing bury2:

      [C] [B] [A] bury2 == [A] [C] [B]

    we could find a worst-case by using an abstraction algorithm:

       A\ B\ C\ [A] [C] [B]

    == A\ B\ [[A]] dip [B]

    == A\ [[[A]] dip] dip

    == [A\ [[A]] dip] cons dip

    == [[A\ [A]] cons dip] cons dip

    == [[] cons dip] cons dip

    And then, and we try this program out and count how many steps it takes:

       [C] [B] [A] [[] cons dip] cons dip

    == [C] [B] [[A] [] cons dip] dip

    == [C] [A] [] cons dip [B]

    == [C] [[A]] dip [B]

    == [A] [C] [B]

    Depending on the exact way in which steps are counted, you might this consider

    this to take 7 steps. Then, because of this, we don't have to waste any more

    than 7 steps on a non-terminating program, because after that we know it could

    not be the fastest, even if it did eventually terminate. Also, our search will

    be over once we finish programs larger than size 7, because all programs bigger

    than that will take longer than 7 steps to finish (at least in a certain

    formalization of "steps"), assuming each word is executed at least once (and, if

    some words are unused, then that program obviously could not be the fastest).

    Of course, that's all just theoretical. Really, a brute-force search is totally

    impractial for large programs, due to the exponential slowness (perhaps this

    could change someday though, with quantum computing, but if I understand right,

    even quantum computing cannot solve an exponential problem in linear time).

    - Brent

## e1_t — 2002-04-05 00:04:29

    --- In concatenative@y..., John Carter <john.carter@t...> wrote:

     > > > This also allows to define the concept of power of a base.

    > > >

    > > > Given a set of defining programs, the most powerful base is

     that for which

     > > > the corresponding GOA's, in some sense eg. minimax, average,...

     are the

     > > > shortest.

    > >

    > > Yes, that is a useful notion. But do keep in mind that all sorts

     of

     > > very mature optimising compilers (for other languages) exist which

    > > only aim for what is third-best  - and know that even second-best

    > > takes just far too long to find.

    >

    > Ah, but what do optimising compilers compile into. Machine

     instructions.

     > There are two views of machine instructions - CISC and RISC.

    >

    > CISC means have lots of powerful instructions.

    > RISC means have a few instructions you really need and make them

     fast.

     >

    > A powerful base would be the best of both worlds.

    >

     I don't completely follow. What does that have to do with the fact

    that compilers compile into machine code? Unless you're planning on

    creating your own virtual machine your compiler will have to do the

    same. Having said that I always had a view that hardware should not

    be made to run software but the other way around. There are some

    exceptions though. Chuck Moore's processors are a good example but

    again he didn't make his processors suited to Forth more so than C.

    He simply made a decision to use stack instead of registers. Doing

    that doesn't cripple C compilers or any other compilers - it does

    make Forth interpreters shine though (note that I said interpreters -

    a Forth compiler is really no different to any other compiler - it

    can be made equally efficient on any platform).

    The fact that compilers target a certain architecture (CISC or RISC,

    it doesn't matter really) has nothing to do with them aiming for

    third-best. Having a CISC/RISC combo architecture (I guess these days

    x86 processors would qualify into that category since their

    instruction set is CISC but internally they're RISC processors)

    wouldn't improve compilers ability to generate better code. So at

    least at the lowest level it doesn't matter what base you use.

    Compilers will continue aiming for third-best.

    It's up to the compilers for the new generation of functional

    languages to (try to) look for second-best.

    One final note is that many of today's RISC processors actually have

    more instructions than CISC processors. PowerPC instruction set is

    bigger than x86 instruction set (I didn't verify this but I've been

    told that's the case - or at least it was the case before MMX,

    3DNow!, SSE, SSE2,...).

     >

    > John Carter                             Phone : (64)(3) 358 6639

    > Tait Electronics                        Fax   : (64)(3) 359 4632

    > PO Box 1645 Christchurch                Email : john.carter@t...

    > New Zealand

    >

    > Zeitgeist shutting down for corrective maintenance, please log off.

## John Carter — 2002-04-05 06:55:45

    On Fri, 5 Apr 2002, e1_t wrote:

     > > There are two views of machine instructions - CISC and RISC.

    > >

    > > CISC means have lots of powerful instructions.

    > > RISC means have a few instructions you really need and make them

    > fast.

    > >

    > > A powerful base would be the best of both worlds.

    > >

    >

    > I don't completely follow. What does that have to do with the fact

    > that compilers compile into machine code?

      >snip<

    > Chuck Moore's processors are a good example but

    > again he didn't make his processors suited to Forth more so than C.

    > He simply made a decision to use stack instead of registers. Doing

    > that doesn't cripple C compilers or any other compilers - it does

    > make Forth interpreters shine though (note that I said interpreters -

    > a Forth compiler is really no different to any other compiler - it

    > can be made equally efficient on any platform).

     OK, this of "powerful base" idea would only apply in the...

     * very unlikely event that you were designing a new CPU and instruction

       set or...

     * the much more likely event you were designing a byte code for a

       compiled to byte code language + byte code interpreter language.

    How does one decide what instructions to implement? Well, last time I did

    that, I wrote the parser and then compiled it into smallish chunks. Some

    chunks were actually very very large, but then that was what that the

    language was about. It made access to some very bizarre semantics easy.

    The large chunks were just a low level interface to the bizarre semantics.

    All very top-down and completely and utterly one-shot single purpose.

    Now if one were to design a general purpose byte code language (parrot,

    c--, gcc RTL, etc) wouldn't it be better to choose the most powerful and

    expressive byte codes to implement.

    There is a trade-off. The more byte-codes the less work for the compiler

    writer and the more work for the interpreter writer.

    In fact, if you are using the byte code as a portable intermediate

    representation (think UCSD pascal pcode) the effort is proportional to

    number of byte codes * number of platforms ported to.

    The GNU gcc project has a brute force tool that seeks the most time wise

    efficient implementation of a code fragment. Typically for converting their RTL

    intermendiate language into the machine language.

    Now wouldn't it be nice to have a brute force search for the most powerful

    base.

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Zeitgeist shutting down for corrective maintenance, please log off.

## Manfred von Thun — 2002-04-08 03:26:45

    On -1 xxx -1, Brent L Kerby wrote:  [probably 4-APR-2002]

     > > [impossibility of finding the shortest program that does a certain thing]

     [..]

     > algorithm, sadly). The thing that makes the problem impossible, even by

    > brute-force search (starting with the smallest programs and working upward) is

    > that in the course of the brute search, we are bound to try a non-terminating

    > program, on which we will get stuck forever.

     I think there is a quite separate reason which has to do with the

    rewriting based on the equivalence of various programs.

    Suppose that we write all rewriting explicitly:

      LHS  ==>  RHS

    If all the rewriting rules are like definitions, and are being used in the

    direction of expanding the RHS, then there is no problem:

      a  ==>  b c d                          or whatever

    If there are some non-definitional rewrite rules in which the RHS is

    at least as long as the LHS, then again no problem:

      a b  ==>  c d e

    But if there are rules in which the RHS is shorter than the LHS,

    like this:

      a b c  ==>  d

    then an exhaustive search for short programs will have to consider

    longer and longer programs which are in fact longer than the shortest

    already found.

    (I'll mention one such rule which I stumbled upon a while back:

      swap [i] dip  ==  dip)

    This is a perennial problem with rewriting systems, and is - as far

    as I know - the main source of algorithmic unsolvability.

    Something similar explains why propositional logic is decidable but

    predicate logic is not: for the latter any proof might have to  contain

    formulas that are not subformulas of other ones already occurring

    but are actually longer than any already occurring.

    Sorry if this was not too clear. It has been years since I read about

    rewriting systems.

    [.. more good things]

     > - Brent

       - Manfred