For the record, Bill: Turns out Google does not make systems so stable that they never crash. When you run computations that are distributed over 1000 machines, even "stays up months at a time" means a machine you're using will die every hour. Instead we have computational infrastructure that targets handing the failure gracefully, only re-running the 0.1% of the work that gets lost. --Michael On Tue, Jan 17, 2017 at 12:56 AM, Bill Gosper <billgosper@gmail.com> wrote:
Rohan requested all 7581 monotonic pentadic boolean functions. Instead of reading up on the smart way to do this (Vol IV?), I built a little sandbox, iteratively Outer Anding and Outer Oring the initial pool {0,p,q,r,s,t,1} with itself. Interestingly, if one Outerand is always {0,p,q,r,s,t,1}, this only finds 7580. The missing one is easy to guess. For brevity, we illustrate with the triadics:
In[384]:= three = alg2bool /@ {0, p, q, r, 1}
Out[384]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, (#1[[1]]; True) &}
(For philosophical reasons, the constants True and False are monadic (vs nulladic.) What is the truth table of a constant?)
ttab is truth table: In[385]:= ttab /@ three
During evaluation of In[385]:= Transpose::nmtx: The first two levels of {} cannot be transposed.
(A harmless glitch.) Out[385]= {{False}, {False, True}, {False, True, False, True}, {False, True, False, True, False, True, False, True}, {True}}
In[386]:= three;
cull is just delete duplicates by truth table. tim prints time and length. In[387]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim
During evaluation of In[387]:= 6.*10^-6,5 (6 μs, 5 fcns)
During evaluation of In[387]:= 0.000064,25
During evaluation of In[387]:= 0.015481,8
During evaluation of In[387]:= 0.000063,25
During evaluation of In[387]:= 0.002756,8
During evaluation of In[387]:= 0.020625,11 (Redundantly culling smaller pieces saves time.)
Out[387]= {(#1[[1]]; False) && (#1[[1]]; False) &, (#1[[1]]; True) && (#1[[1]]; True) &, #1[[1]] && #1[[1]] &, #1[[1]] && #1[[ 2]] &, #1[[1]] && #1[[3]] &, #1[[2]] && #1[[2]] &, #1[[2]] && #1[[ 3]] &, #1[[3]] && #1[[3]] &, #1[[1]] || #1[[2]] &, #1[[1]] || #1[[ 3]] &, #1[[2]] || #1[[3]] &}
This brought us up to 11 functions. Rub these against the original 5: In[388]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim
During evaluation of In[388]:= 0.000013,11
During evaluation of In[388]:= 0.000124,55
During evaluation of In[388]:= 0.031731,15
During evaluation of In[388]:= 0.00013,55
During evaluation of In[388]:= 0.007292,15
During evaluation of In[388]:= 0.044341,19
Out[388]= {(#1[[1]]; False) && ((#1[[1]]; False) && (#1[[1]]; False)) &, (#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)) &, (#1[[1]]; True) && (#1[[1]] || #1[[2]]) &, (#1[[1]]; True) && (#1[[1]] || #1[[3]]) &, (#1[[1]]; True) && (#1[[2]] || #1[[3]]) &, #1[[ 1]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 1]] && (#1[[1]] && #1[[2]]) &, #1[[ 1]] && (#1[[1]] && #1[[3]]) &, #1[[ 1]] && (#1[[2]] && #1[[3]]) &, #1[[ 1]] && (#1[[2]] || #1[[3]]) &, #1[[ 2]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 2]] && (#1[[2]] && #1[[3]]) &, #1[[ 2]] && (#1[[1]] || #1[[3]]) &, #1[[ 3]] && ((#1[[1]]; True) && (#1[[1]]; True)) &, #1[[ 3]] && (#1[[1]] || #1[[2]]) &, #1[[ 1]] || (#1[[2]] && #1[[3]]) &, #1[[ 1]] || (#1[[2]] || #1[[3]]) &, #1[[ 2]] || (#1[[1]] && #1[[3]]) &, #1[[3]] || (#1[[1]] && #1[[2]]) &}
We got 19 of the 20. But when we try again, In[389]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, three, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, three, %] // Flatten // tim] // tim]] // tim
During evaluation of In[389]:= 0.000017,19
During evaluation of In[389]:= 0.000214,95
During evaluation of In[389]:= 0.063244,19
During evaluation of In[389]:= 0.000211,95
During evaluation of In[389]:= 0.016854,19
During evaluation of In[389]:= 0.090048,19 . . . we stick at 19.
The solution is to Outer with the first iterate, In[458]:= bool2alg /@ %387
Out[458]= {0, 1, p, p q, p r, q, q r, r, p + q, p + r, q + r}
rather than {0, p, q, r, 1}, the 0th.
In[390]:= cull[Union[% // tim, cull[Outer[Distribute[And[#1, #2], Function] &, %387, %] // Flatten // tim] // tim, cull[Outer[Distribute[Or[#1, #2], Function] &, %387, %] // Flatten // tim] // tim]] // tim
During evaluation of In[390]:= 0.000018,19
During evaluation of In[390]:= 0.000466,209
During evaluation of In[390]:= 0.200324,20
During evaluation of In[390]:= 0.00059,209
During evaluation of In[390]:= 0.037646,20
During evaluation of In[390]:= 0.248116,20
Out[390]= {((#1[[1]]; False) && (#1[[1]]; False)) && ((#1[[1]]; False) && ((#1[[1]]; False) && ((#1[[1]]; False) && (#1[[1]]; False)))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]] || #1[[2]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]] || #1[[3]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[2]] || #1[[3]]))) &, ((#1[[ 1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[1]] || (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[1]] || (#1[[2]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[2]] || (#1[[1]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && ((#1[[1]]; True) && (#1[[3]] || (#1[[1]] && #1[[2]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && ((#1[[1]]; True) && (#1[[2]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[1]] && #1[[2]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[1]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 1]] && (#1[[1]] && (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && ((#1[[1]]; True) && (#1[[1]] || #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 2]] && (#1[[2]] && (#1[[2]] && #1[[3]]))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 3]] && ((#1[[1]]; True) && ((#1[[1]]; True) && (#1[[1]]; True)))) &, ((#1[[1]]; True) && (#1[[1]]; True)) && (#1[[ 3]] && ((#1[[1]]; True) && (#1[[1]] || #1[[2]]))) &, (#1[[ 1]] || #1[[2]]) && ((#1[[1]]; True) && (#1[[3]] || (#1[[1]] && #1[[2]]))) &}
The last one: In[391]:= bool2alg@%[[-1]]
Out[391]= (p + q) (p q + r)
is not obviously symmetric. In[392]:= ttab@%%[[-1]] == ttab@alg2bool[p q + p r + q r]
Out[392]= True
Note that this function is insensitive to swapping And with Or: In[459]:= p q + p r + q r /. {Times -> Plus, Plus -> Times}
Out[459]= (p + q) (p + r) (q + r)
In[460]:= bool2alg@alg2bool@Expand@%
Out[460]= p q + p r + q r + p q r
(I didn't write a simplifier, but the p q r is clearly redundant.)
The 7581st function was (p + q + r) (p + q + s) (p + r + s) (q + r + s) (p + q + t) (p + r + t) (q + r + t) (p + s + t) (q + s + t) (r + s + t) == p q r + p q s + p r s + q r s + p q t + p r t + q r t + p s t + q s t + r s t
While guessing and testing this, the all-day (46000 second) cull finished. But I was a couple of minutes bringing up the window, and the PoS OSX decided to reboot. This was almost certainly not a hardware error. Tom Knight told me Microsoft and Apple don't even try to makes stable environments. Symbolics Genera stayed up months at a time. If anyone from Symbolics offered to teach the big guys how to make stable systems, they would have been shown the door. But I bet Google knows how to do it.
Code: In[376]:= Clear@bool2alg; bool2alg[bool_] := (bool /. {False -> 0, True -> 1, And -> Times, Or -> Plus})@{p, q, r, s, t} /. x_^_ :> x
In[377]:= five = {(#[[1]]; False) &, #[[1]] &, #[[2]] &, #[[3]] &, #[[ 4]] &, #[[5]] &, (#[[1]]; True) &}
Out[377]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, #1[[ 4]] &, #1[[5]] &, (#1[[1]]; True) &}
In[378]:= bool2alg /@ %
Out[378]= {0, p, q, r, s, t, 1}
In[448]:= Clear@alg2bool; alg2bool[exp_] := exp //. Except[0, _Integer] :> 1 /. { 0 -> ((#1[[1]]; False) &), 1 -> ((#1[[1]]; True) &)} /. S : (p | q | r | s | t) :> (#[[x]] & /. x :> Evaluate@(Position[{p, q, r, s, t}, S][[1, 1]])) /. {Times -> And, Plus -> Or} //. f : (And | Or)[Function[_] ..] :> Distribute[f, Function]
In[380]:= alg2bool /@ %%
Out[380]= {(#1[[1]]; False) &, #1[[1]] &, #1[[2]] &, #1[[3]] &, #1[[ 4]] &, #1[[5]] &, (#1[[1]]; True) &}
In[381]:= Clear@ttab; ttab[fn_] := shrink[fn /@ Block[{n = Cases[fn, HoldPattern@Part[_, n_] :> n, 99] // Max}, PadLeft[#, n, False] & /@ (IntegerDigits[#, 2] & /@ Range[0, 2^n - 1]) /. {0 -> False, 1 -> True}]]
In[382]:= shrink[L_List] := NestWhile[Transpose[Partition[#, 2]][[1]] &, L, Riffle[#2, #2] == #1 &, 2, \[Infinity], -1]
Clear@cull; cull[L_List] := #[[1]] & /@ DeleteDuplicates[Prepend[ttab@#, #] & /@ L, Rest@#1 == Rest@#2 &] --rwg _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.