A while back I happened to read that someone was working with Wolfram Science on creating a project called "integer base." The idea behind integer base was to try and find the shortest programs that lead to each integer. I got to talk with someone at Wolfram Research who knew a bit about the project, and he told me about how the project was never really gotten to a point where they were ready to share it. There are things to consider like how to decide which program is simpler than another, what functions to allow, etc. They were going to make it so that people could submit their own functions if a person thought they'd found the shortest.

Well anyway, since integer base isn't currently really a thing right now, I decided to do a little searching within "program space" myself just for fun. I can't say that my way of doing a sort of "proto-integer base" is the best at all, but it's maybe a start.

I restricted myself to just one kind of simple program, combinators. Combinators are a kind of function which are interesting to me because there are just two combinator functions, called the "S" and "K" combinators, with which one can in principle write any program (they are together "Turing complete.")

The two combinator functions can be defined as s[x][y_][z]:=x[z][y[z]] and k[x][y]:=x. One can visualize a combinator evaluating step by step for example like this:

Since combinators include just two functions, it was easy to enumerate every possible combinator up to a certain size. All combinators below size 6 reach a state where applying the functions no longer changes the combinator, and essentially the computation terminates. There are exactly two size 7 combinators which don't terminate. I figured out what "fixed point" each combinator up to size 7 reached, then made a list where "s" became 1 and "k" became 0, and determined which integer each final combinator state corresponded to. In this way, I was able to assign a number to every possible size 7 combinator expression which terminated.

Each number had a corresponding combinator (this has to be the case since a combinator of a form such as w_[x_[y_[z_]]] never matches any of the rules, and so can always represent any number with the right choice of s's and k's. But I was interested in combinators which grew, so for example s[s][k][k] becomes s[k][k][k], but if this were the smallest combinator which leads to the number 8, ({1,0,0,0}) I wouldn't count it since the combinator didn't grow (in essence one isn't getting more than one puts in the function.) Not all integers had a combinator that had to grow to become that number.

Anyway, here are some of my results, showing the smallest combinators which grew to represent a certain integer.

And here is the code I wrote to find these results:

evaluateCombinatorList[init_, rule_, maxIterations_: Infinity, 
  maxSize_: Infinity] := 
 NestWhileList[# /. rule &, init, 
  UnsameQ[##] && LeafCount[#2] < maxSize &, 2, maxIterations]

treeToFunctions[tree_] := ReplaceRepeated[tree, {x_, y_} :> x[y]]

allTrees[list__] := 
 Join @@ ReplaceList[{list}, {x__, y__} :> 
    Tuples@{allTrees[x], allTrees[y]}]
allTrees[x_] := {x}

enumeratedCombinators[maxSize_] := 
 treeToFunctions /@ 
  Flatten[allTrees @@@ 
    Flatten[Table[Tuples[{k, s}, i], {i, maxSize}], 1], 1]

combinatorSymbols[combinator_] := 
 Flatten[out = combinator //. x_[y_] :> {x, y}; 
  If[! ListQ[out], {out}, out]]

combToInt[combinator_] := 
 FromDigits[combinatorSymbols[combinator] /. {s -> 1, k -> 0}, 2]

evaluations = 
  Select[With[{evaluation = 
        evaluateCombinatorList[#, {k[x_][y_] :> x, 
          s[x_][y_][z_] :> x[z][y[z]]}, 100, 1000]}, 
      With[{result = Last[evaluation]}, <|"init" -> #, 
        "evaluation" -> evaluation, "result" -> result, 
        "integer" -> combToInt[result]|>]] & /@ 
    enumeratedCombinators[7], SameQ @@ #["evaluation"][[-2 ;;]] &];

firstInts = 
  Function[int, FirstCase[evaluations, _?(#["integer"] == int &)]] /@ 
   Union[#["integer"] & /@ evaluations];

(KeyDrop[#, "evaluation"] & /@ 
    Select[firstInts, 
     LeafCount[#["result"]] > LeafCount[#["init"]] &])[[;; 
   100]] // Column

I also thought about the fact that I am in a sense ignoring some information in the combinator output, since for example k[k[s[s]] corresponds to a binary sequence {0,0,1,1}, and by converting this directly to a number the leading zeros are ignored. I wrote a second version of my code which might be called "binary sequence base" where basically I just added a leading 1 to all the outputs, so that k[k[s[s]] now becomes {1,0,0,1,1}. Also, in that case, I found that having s correspond to 0 instead of 1 worked better in that case (gave smaller and more output numbers.) The code is similar to what I have posted above, and I have attached it to this post.

Attachments: