Digital transforms=nor-formula=-ANN lesson=imitative synapse formula.
This obvious yet critical theorem is probably known under other names. A quote I have grown to accept: "At first they said it was absurd, then obvious, then well known".
Language:
a 'finite binary vector' is for example 1,1,0,1,0. More generally, b1,b2,b3, ... bn where bi=1 or 0 and 'n' is a finite integer called its dimension. The desired interpretation is bi, is the stimulation state(high or low) of the ith wire or nerve.
Finally, a function f(x)=y defines a set of pairs: (xj, yj). or as vector pairs: ([xj1, xj2, ...xjn], [yj1,yj2, ... yjm]) where n, m are dimensions.
Concept:
For example, a properly working computer programmed to display(with a large number of pixel bits) the square of its typed input will perform simply and consistently(repeat the same display for the same input) for all inputs up to a certain size.; For input too large it will complain, consistently. One might sneer, if the display includes the date, the display is inconsistent[non-repetitive]. I must then add, 'input' is meant to be all inclusive, it includes the time and date so 'one', for rigor, would have to reset the clock with each input number and type with the same speed. To continue, the program could be a table of all the possible input numbers paired with the answers or simply a very large addressed digital computer memory. The theorem just shows that a fixed 'associative memory' or 'ROM memory' may be just 'nors' specifically wired up. I refer to 'nors' since all the logic functions of a computer can be constructed from them.
Theorem:
For any 1 to 1 mapping of a set of p finite binary vectors of dimension n,
{x1, x2, ... xp}, onto p finite binary vectors of dimension m, {y1, y2, ... yp}, by a function, f(x)=y,
there exists an equal finite, fixed propositional logic function, F(x)=y.
Proof:
The general idea is to make intermediate logic functions, Ej(z), =1 or =0 as z=xj or not. Then construct y from E, by having E keep the non-zero components of only that y = f(x).
Explicit finite construction:
Ej(z)= ( z1 and xj1) and ( z2 and xj2) and ... where zi is the ith component of z and xji is the ith component of the jth x. So Ej(z)=1 if z=xj and Ej(z)=0 if z not = xj.
Finally, F(x)= (y1,1 and E1(x)) or (y2,1 and E2(x)) or ... (yn,1 and En(x)),
(y1,2 and E1(x)) or (y2,2 and E2(x)) or ... (yn,2 and En(x)), ... . where yj,i is ith component of transform of jth x. So F(xj)=yj=yj,1, yj,2, yj,3, ... yj,m.
Expansion to Learning:
It's clear that learning may correspond to changing a digital transform. For example, one may follow curiosity to touch a glowing, hot light bulb, once. Thereafter, curiosity is changed to other things.
So I'll define consistent digital learning as reproducible changes in the transform due to previous digital input. But to easily use the above theorem which does not explicitly have learning, serial input or serial output, 'previous digital input' or 'serial input' may be incorporated in a combined, simultaneous or multiplexed input as original, serial inputs tagged with their original date so the original serial input may be exactly recovered from a combined simultaneous input. Similarly for the output, serial output may be tagged with its date and paralleled with others so there is no information lost so any process that needs an ordered serial input may use a similar demultiplexer. Again for simplicity of 'reproducibility', I assume equal intelligences are started or restarted as if they have had no experience, no previous input. Then after being given the multiplexed input, if they respond the same, they are called consistent learners. And so a consistent learning system using a simple demultiplexer on a single simultaneous input reproducing one's total learning experience and a multiplexer to combine one's output into a larger simultaneous output is just another example of a digital transform which is equal to a nor-formula.
Expansion to Recursion:
Here I rely on the finite cycle period of a finite memory deterministic computer.Computer cycling: Recursion is deterministic digital computers that in series set some or all their inputs to their outputs. This can be treated similar to the above 'learning'. Consider 2 finite parts of the output: First, a sequence of binary numbers up to the first one that is later repeated. Second, one cycle of the sequence that is endlessly repeated. Then the recursive automaton can be replaced by a single large memory that takes as address the finite multiplex of all the information in the inputs( initial and the 2 output parts feedback) and recovers from this single addressed memory cell the multiplex of the 2 output parts. To get 'endless' cycling of part 2 of output, after the first part, the demultiplexer is made to repeat the second part endlessly.
Efficiency[ 3 mar 98]:
Prof. McGill conceded 'only nor-formulas are required' but 'infinite techniques and math induction are more efficient'. I could not think of an answer right away. But a computerized axiom-proof system may be seen as selections of axioms translated into finite numbers and a proof system implemented by a finite nor-formula that digitally transforms these axiom numbers into nor-formula theorems. The 'selection' of the axioms may be another digital transform of a digitized problem. And of course another axiom-proof system may be used. Thus insofar as the axiom-proof is 'efficient', their is an equally efficient nor-formula. This efficiency may just be number of required nor-gates.
=-ANN: artifical negative feedback neural net lessons[13Mar98]: Try it out.
This will also be a simple constructive proof. As is standard in -ANN lessons, we designate an extra nerve, not used as digital input-output, as a formula activator nerve which is stimulated when the synapse formula is to be applied to designated input nerves and generate the desired output on another set of nerves.
First we teach a copy synapse from a 1st copy of the 'name' to each '1' nerve in the output and to a 'recognition' nerve. Then for each required '0' in the input, we teach a synapse to inhibit the 'names' 1st copy nerve. Finally for each required '1' in the input we teach an inhibit of a 2nd copy of the 'name' which inhibits the 1st copy. Thus the output will be all '0' for any other input for this 'name'. To get any full digital transform defined for all possible numbers of a given number of digits one teaches a transform as just described for each IO pair. Then one teaches a compound 'name' nerve that is copied to all constituent 'names'. But to prevent a union of outputs, each 'recognition' nerve must be tought to inhibit the other constituent names. As is required for -ANN extensibility, each required synapse is augmented by an extra nerve and 'copy' type synapse and a unique 'name' nerve so the input or output of the required synapse may be inhibited and so removed from interference in learning new synapses.
Interactive integer based differentiation. (10k) General simple example of explicit finite nor-formula interpretation of differentiation(relative rates of change).
Rigorous math in nor-formulas.(10k) Example of super-rigorous translation of set operations and relations into nor-formulas.
E-mail author: R Massey for additions Oct 2003.
top/home (40k)