Jonathan’s combinator
Jonathan’s combinator
In[]:=
klike=s[s[x][y][s]][s[y][s][x]][s[s][x][y]];
In[]:=
interpreter={x_[s][y_[s]][s[y_][x_[y_]]][y_[x_][s[x_]][s[y_][x_[y_]]]]x}
Out[]=
{x_[s][y_[s]][s[y_][x_[y_]]][y_[x_][s[x_]][s[y_][x_[y_]]]]x}
In[]:=
SKFixedPointEvolveList[s[s[x][y][s]][s[y][s][x]][s[s][x][y]]]/.interpreter
Out[]=
{s[s[x][y][s]][s[y][s][x]][s[s][x][y]],s[x][y][s][s[s][x][y]][s[y][s][x][s[s][x][y]]],x[s][y[s]][s[s][x][y]][s[y][s][x][s[s][x][y]]],x[s][y[s]][s[y][x[y]]][s[y][s][x][s[s][x][y]]],x[s][y[s]][s[y][x[y]]][y[x][s[x]][s[s][x][y]]],x}
In[]:=
SKFixedPointEvolveList[s[s][k][k][s]]
Out[]=
{s[s][k][k][s],s[k][k[k]][s],k[s][k[k][s]],s}
In[]:=
SKFixedPointEvolveList[s[s][k][k][s]/.kklike]/.interpreter
Out[]=
s[s[x][y][s]][s[y][s][x]][s[s][x][y]];
In[]:=
SKStep[expr_]:=MapAt[Replace[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x}],expr,{First[Sort[Position[expr,s[_][_][_]|k[_][_]]],{}]}]
In[]:=
GeneralFixedPointEvolveList[f_,expr_,max_Integer]:=Most[NestWhileList[f,expr,#1=!=#2&&LeafCount[#2]<max&,2]]
In[]:=
LeafCount/@GeneralFixedPointEvolveList[MapAt[Replace[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]s[s[x][y][s]][s[y][s][x]][s[s][x][y]]}],#,{First[Sort[Position[#,s[_][_][_]|k[_][_]]],{}]}]&,s[s][k][k][s],100]/.interpreter
Out[]=
{5,5,5,19,24,24,29,40,42,53,63,66,68,68,70,70,72,82,85,85,87,97}
Basic structure:
Basic structure:
k = something in terms of s
Two other items: harness; decoder