|
Search: id:A064436
|
|
|
| A064436 |
|
Number of switching functions of n or fewer variables which cannot be realized as threshold gates. |
|
+0
5
|
|
| 0, 0, 2, 152, 63654, 4294872724, 18446744073694523482, 340282366920938463463374607423390140592, 115792089237316195423570985008687907853269984665640564039457583990351590086990
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
The corresponding systems of linear inequalities are not solvable: linearly non-separable truth or switching functions. Truth functions which ar "non-neurons", and are realizable only as two levels threshold gate networks.
|
|
FORMULA
|
a(n)=2^(2^n)-A000609(n)
|
|
EXAMPLE
|
n=2: out of the 16 B^2 -> B^1 truth functions, 14 are linearly separable; the 2 exceptions are XOR and its negation: f[x,y]=!xz+x!y and !f[x,y]=xy+!x!y. So a(2)=2. With increasing n, the chance that a switching function belongs to this sequence tends to 1.
|
|
CROSSREFS
|
A000609.
Sequence in context: A024245 A113576 A102458 this_sequence A012605 A012602 A000725
Adjacent sequences: A064433 A064434 A064435 this_sequence A064437 A064438 A064439
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Labos E. (labos(AT)ana.sote.hu), Oct 01 2001
|
|
|
Search completed in 0.002 seconds
|
