Functional Completeness

In[]:=
FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{And->2,Xor->2}]&/@Tuples[{a,b},3]]
Out[]=
{12,12,0,0,0,0,12,12,8,8,0,4,6,4,10,10,8,8,4,4,4,4,10,10,8,8,2,0,2,6,12,12,8,8,4,0,4,6,10,10,8,8,2,2,2,2,12,12,8,8,0,2,6,2,12,12,10,10,0,0,0,0,10,10}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{And->2,Xor->2}]&/@Tuples[{a,b},n]],{n,5}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[NotFound]}
In[]:=
With[{u=Table[ParallelMap[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&,Flatten[Groupings[#,{And->2,Xor->2}]&/@Tuples[{a,b},n]]],{n,6}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[NotFound]}
In[]:=
With[{u=Table[ParallelMap[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&,Flatten[Groupings[#,{And->2,Xor->2}]&/@Tuples[{a,b},n]]],{n,7}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[NotFound]}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Not->1,Xor->2}]&/@Tuples[{a,b},n]],{n,3}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,1},1Missing[NotFound],2Missing[NotFound],3{1,1},4Missing[NotFound],5{1,2},6{2,11},7Missing[NotFound],8Missing[NotFound],9{2,12},10{3,113},11Missing[NotFound],12{3,1},13Missing[NotFound],14Missing[NotFound],15{2,2}}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Not->1,Xor->2}]&/@Tuples[{a,b},n]],{n,4}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,1},1Missing[NotFound],2Missing[NotFound],3{1,1},4Missing[NotFound],5{1,2},6{2,11},7Missing[NotFound],8Missing[NotFound],9{2,12},10{3,113},11Missing[NotFound],12{3,1},13Missing[NotFound],14Missing[NotFound],15{2,2}}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Implies->2,Xor->2}]&/@Tuples[{a,b},n]],{n,5}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1{3,22},2{4,100},3{3,4},4{4,60},5{3,13},6{2,4},7{3,12},8{5,363},9{4,68},10{1,2},11{2,3},12{1,1},13{2,5},14{3,25},15{2,1}}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Implies->2,Not[Xor[#1,#2]]&->2}]&/@Tuples[{a,b},n]],{n,5}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0Missing[NotFound],1Missing[NotFound],2Missing[NotFound],3Missing[NotFound],4Missing[NotFound],5Missing[NotFound],6Missing[NotFound],7Missing[NotFound],8{3,14},9{2,4},10{1,2},11{2,3},12{1,1},13{2,5},14{3,19},15{2,1}}
In[]:=
With[{u=Table[ParallelMap[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&,Flatten[Groupings[#,{Xor->2,Not[Xor[#1,#2]]&->2}]&/@Tuples[{a,b},n]]],{n,6}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,1},1Missing[NotFound],2Missing[NotFound],3{3,3},4Missing[NotFound],5{3,11},6{2,3},7Missing[NotFound],8Missing[NotFound],9{2,4},10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14Missing[NotFound],15{2,2}}
With[{u=Table[ParallelMap[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&,Flatten[Groupings[#,{Xor->2,Not[Xor[#1,#2]]&->2}]&/@Tuples[{a,b},n]]],{n,7}]},Table[i->FirstPosition[u,i],{i,0,15}]]
In[]:=
With[{u=Table[ParallelMap[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&,Flatten[Groupings[#,{And->2,Not->1}]&/@Tuples[{a,b},n]]],{n,5}]},Table[i->FirstPosition[u,i],{i,0,15}]]
In[]:=
$Version
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Nand->2,Xor->2}]&/@Tuples[{a,b},n]],{n,4}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1{4,57},2{4,300},3{2,1},4{4,60},5{2,7},6{2,4},7{2,3},8{4,205},9{3,13},10{1,2},11{3,10},12{1,1},13{3,9},14{4,125},15{3,1}}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Nand->2,Xor->2}]&/@Tuples[{a,b},n]],{n,3}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,2},1Missing[NotFound],2Missing[NotFound],3{2,1},4Missing[NotFound],5{2,7},6{2,4},7{2,3},8Missing[NotFound],9{3,13},10{1,2},11{3,10},12{1,1},13{3,9},14Missing[NotFound],15{3,1}}
In[]:=
With[{u=Table[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Flatten[Groupings[#,{Nand->2,Nor->2}]&/@Tuples[{a,b},n]],{n,6}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{3,5},1{2,4},2{3,16},3{2,1},4{3,13},5{2,7},6{6,7735},7{2,3},8{4,60},9{6,6845},10{1,2},11{3,10},12{1,1},13{3,9},14{4,50},15{3,1}}
In[]:=
With[{u=ParallelTable[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Union[Flatten[Groupings[#,{And->2,Xor->2}]&/@Tuples[{a,b},n]]],{n,7}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,1},1Missing[NotFound],2{3,5},3Missing[NotFound],4{3,4},5Missing[NotFound],6{2,6},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,71},15Missing[NotFound]}
In[]:=
With[{u=ParallelTable[FromDigits[Boole[BooleanTable[#,{a,b}]],2]&/@Union[Flatten[Groupings[#,{Or->2,Xor->2}]&/@Tuples[{a,b},n]]],{n,7}]},Table[i->FirstPosition[u,i],{i,0,15}]]
Out[]=
{0{2,1},1Missing[NotFound],2{3,16},3Missing[NotFound],4{3,20},5Missing[NotFound],6{2,6},7Missing[NotFound],8{4,99},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{2,3},15Missing[NotFound]}

Forward Computation

Single Point Mutation

“Pick reasonable rules” [ perhaps Nand and Nor ]
Some problems can be solved with single point mutation
Which problems can be solved? Look at learning curves

Summarize “what can solve what?” [with how much training?]

Given a solution, can look at activation plot [i.e. change one bit; what happens?]

Draw rule arrays that compute each Boolean function

Give the inputs next to each other ... but leave some empty space for computation...
[ Find the simple “template” [rule array] for each Boolean function ]
{0,a,b,0}->{0,f[a,b],0,0}
(* may need extra zeros *)

Exhaustive Search

[ Whole array ]
Lifetime for (2t+1)×t
In[]:=
Table[(2t+1)×t,{t,10}]
Out[]=
{3,10,21,36,55,78,105,136,171,210}
In[]:=
2^21
Out[]=
2097152
Finite width version...
In[]:=
Table[5t,{t,10}]
Out[]=
{5,10,15,20,25,30,35,40,45,50}
Run for 7 steps ... what precisely dies out after 6
How many configurations lead to dying after exactly 6?
In[]:=
RuleArrayFinalState[][CenterArray[{1},5],Table[0,4,5],5]
Out[]=
{0,0,0,0,0}
In[]:=
RuleArrayFinalState[][CenterArray[{1},5],Partition[#,5],5]&/@Tuples[{6,14},20];
In[]:=
Count[%,Table[0,5]]
Out[]=
0
In[]:=
Counts[%23]
Out[]=
{0,0,0,1,0}393216,{0,0,0,1,1}655360

Continuous network visualization

Use 21 functions ... but each function is f[ {w1,w2} . {x1, x2} ] + b
(Indicate by breaking hexagon into 3)
[[ Also draw like an ordinary NN, with “wires” ]]

Backpropagation

Sum of these losses :
Weights appear many times across the batch...
[[ Find out how much high layers get adjusted relative to low layers in typical learning, in MLPs ]]

Boolean case

For every element of the rule array, would flipping the rule affect the loss? How does this work averaged over a batch?
One approach is to do this brute force (cf sensitivity plots)
https://www.wolframscience.com/nks/p605--cryptography-and-cryptanalysis/
https://www.wolframscience.com/nks/notes-10-10--backtracking-in-cellular-automata/
In general, the reversal is a multiway system
(For an ϵ change, the successive changes multiply)
(a+be) +/- (c + de) = (a +/- c) + (b +/-d)e
The inversion is multiway..
Need a multiplexer ...
Consider possible rules f and g...
[[ We need a hexagonal rendering of the above ]]
Richard’s version:
Multiplex between Xor and And:
This assumes the same w everyone....

Boolean backpropagation

Ground truth is based on thresholding the sensitivity function ... and probably attenuating to flip only the top 10% (say) of sensitivities... [ Note that the “derivatives” are done independently, which works for ϵ continuous function, but is only an approximation here ] [ Reflected in the fact that Grad applies independently to each variable ]
What algorithm approximates this?
Could just sample a few, and flip the highest sensitivity cases ...