Message Boards Message Boards

Smallest program that leads to each integer

GROUPS:

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:

enter image description here

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.

enter image description here

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:
POSTED BY: Eric Parfitt
Answer
8 months ago

Hi Eric,

Interesting topic, but I have to contradict your definition:

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.")

According to my dictionary ( not the standard ): A combinator is any function-valued function where each argument is itself a function. This definition is sufficient to ensure that: any evaluation of a combinator is again a combinator. Then, combinatory logic is a system for ennumerating combinators given a set of function definitions and an axiom. The {S,K} system is a special combinatory logic with two combinators, each having one definition. As noted in NKS it's possible to emulate the same system using one combinator with two definitions, for example:

AXIOM = F[F][F[F]][F[F]][F[F][F[F][F]]][F[F][F]];
RULE = {F[F][x_][y_][z_] :> x[z][y[z]], F[F[F]][x_][y_] :> x};

CountF[Comp_] := Length@DeleteCases[Characters[ToString[Comp]], "]" | "["]
CountF /@ NestList[# /. RULE &, AXIOM, 24]
Out[] = {14, 17, 18, 26, 37, 48, 62, 89, 130, 185, 257, 351, 510, 747, 1046, 
1405, 1873, 2577, 3598, 5004, 6804, 9016, 11820, 15729, 21134}

Lately I've been thinking that it's advantageous to just use one combinator. With only one function head, the range of valid combinators is in a one-to-one map with rooted ordered trees, which can be constructed in subsets according to number of nodes:

RootedTrees[0] = {F[]}
RootedTrees[N_] := Union@Flatten[ Flatten[
Outer[F, Sequence @@ (# /. n_Integer :> RootedTrees[n - 1]), 
1]] & /@ Flatten[Permutations /@ IntegerPartitions[N], 1], 1]
(*Catalan Numbers*)Length@RootedTrees[#] & /@ Range[10]

Some people may prefer to write function composition as:

AlternateForm[Combination_] := Combination //. { F[x__] :> Fold[#1@#2 &, F, {x}]} //. {F[] -> F}
AlternateForm[RootedTrees[3]] 
Out[]={F[F[F[F]]], F[F[F, F]], F[F][F[F]], F[F[F]][F], F[F][F][F]}

Defining an ordering for rooted trees puts each combinator into one-to-one mapping with the integers, for example

MapThread[Rule, {Range[0, 22], Prepend[Flatten[RootedTrees[#] & /@ Range[4]], F[]]}]
Out[] ={
0 -> F[], 
1 -> F[F[]], 
2 -> F[F[F[]]], 
3 -> F[F[], F[]], 
4 -> F[F[F[F[]]]], 
5 -> F[F[F[], F[]]], 
6 -> F[F[], F[F[]]], 
7 -> F[F[F[]], F[]], 
8 -> F[F[], F[], F[]], 
9 -> F[F[F[F[F[]]]]], 
10 -> F[F[F[F[], F[]]]], 
11 -> F[F[F[], F[F[]]]], 
12 -> F[F[F[F[]], F[]]], 
13 -> F[F[F[], F[], F[]]], 
14 -> F[F[], F[F[F[]]]], 
15 -> F[F[], F[F[], F[]]], 
16 -> F[F[F[]], F[F[]]], 
17 -> F[F[F[F[]]], F[]], 
18 -> F[F[F[], F[]], F[]], 
19 -> F[F[], F[], F[F[]]], 
20 -> F[F[], F[F[]], F[]], 
21 -> F[F[F[]], F[], F[]], 
22 -> F[F[], F[], F[], F[]]}

Ideally, the ordering would make it easy to take a combinator and return an integer. I haven't quite figured that out yet, but considering the prevalence of Catalan Numbers, I'm sure the answer is out there.

As for Combinator projects, I think there are many interesting possibilities. Highest on the list for me is a computable document solution manual for Smullyan's "To Mock a Mockingbird". I've written algorithms to solve a few of the problems, but haven't had time to get completely through the book. Another possibility along the lines of "integer base" is to identify F ( or other combinators ) with arithmetical functions, and try to compute integers. For example, here are three ways to compute integer 11:

(* 11 =  3*3 + 1 + 1*)
F[F[F[F[F]], F[F[F]]], F, F] //.  F[x_] :> x + 1 //. {F[x_, y_] :> Times[x, y], 
F[x_, y_, z_] :> Plus[x, y, z]} /. F -> 1
(* 11 = 1 + 1 + 1 + 1 +1 + 1 +1 + 1 + 1 + 1 +1 *)
F[F, F, F, F, F, F, F, F, F, F, F] /. {F[x__] :> Plus[x]} /. F -> 1
(* 11 = 1 + (1 + 1) + (1 + 1) + (1 + (1 + (1 + 1))) + (1 + 1)  *)
CommaForm[Comp_] := Comp //. F[x___][y___] :> F[x, y]
CommaForm[Nest[# /. RULE &, AXIOM, 2]]
% //. F[x__] :> Plus[x] /. F -> 1

It would also be awesome to see combinator systems somehow tied in with substitution tilings. What a dream that would be.

POSTED BY: Updating Name
Answer
8 months ago

enter image description here - Congratulations! This post is now Staff Pick! Thank you for your wonderful contributions. Please, keep them coming!

POSTED BY: Moderation Team
Answer
7 months ago

Group Abstract Group Abstract