You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
Functional Completeness
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},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[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},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[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},1Missing[NotFound],2{3,27},3Missing[NotFound],4{3,12},5Missing[NotFound],6{2,4},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,147},15Missing[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},1Missing[NotFound],2Missing[NotFound],3{1,1},4Missing[NotFound],5{1,2},6{2,11},7Missing[NotFound],8Missing[NotFound],9{2,12},10{3,113},11Missing[NotFound],12{3,1},13Missing[NotFound],14Missing[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},1Missing[NotFound],2Missing[NotFound],3{1,1},4Missing[NotFound],5{1,2},6{2,11},7Missing[NotFound],8Missing[NotFound],9{2,12},10{3,113},11Missing[NotFound],12{3,1},13Missing[NotFound],14Missing[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[]=
{0Missing[NotFound],1Missing[NotFound],2Missing[NotFound],3Missing[NotFound],4Missing[NotFound],5Missing[NotFound],6Missing[NotFound],7Missing[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},1Missing[NotFound],2Missing[NotFound],3{3,3},4Missing[NotFound],5{3,11},6{2,3},7Missing[NotFound],8Missing[NotFound],9{2,4},10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14Missing[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},1Missing[NotFound],2Missing[NotFound],3{2,1},4Missing[NotFound],5{2,7},6{2,4},7{2,3},8Missing[NotFound],9{3,13},10{1,2},11{3,10},12{1,1},13{3,9},14Missing[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},1Missing[NotFound],2{3,5},3Missing[NotFound],4{3,4},5Missing[NotFound],6{2,6},7Missing[NotFound],8{2,3},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{4,71},15Missing[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},1Missing[NotFound],2{3,16},3Missing[NotFound],4{3,20},5Missing[NotFound],6{2,6},7Missing[NotFound],8{4,99},9Missing[NotFound],10{1,2},11Missing[NotFound],12{1,1},13Missing[NotFound],14{2,3},15Missing[NotFound]}
Forward Computation
Forward Computation
Single Point Mutation
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?]
Summarize “what can solve what?” [with how much training?]
Given a solution, can look at activation plot [i.e. change one bit; what happens?]
Given a solution, can look at activation plot [i.e. change one bit; what happens?]
Draw rule arrays that compute each Boolean function
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
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
Continuous network visualization
Use 21 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
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
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)
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
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 ...