Let's say we have a function with $m$ arguments
$f(a_1, a_2, .., a_m)$
which produces one of n values at the output (range of the function has cardinality of $n$).
At first (assuming every argument $a_i$ can take the same range of values, $1..k$), there is $k^m$ combinations of input values (i.e. that is cardinality of function's domain). Now, what does it mean that functions are different? If they react identically, then they are not different. If functions are different, there must be a combination of inputs which differentiates between them: when that combination is applied as input, functions produce different values. Applying different inputs can differentiate between the functions! Let's do that.
We put all functions in one group initially and apply the first input value of $k^m$ combinations. Some functions will respond the first value of range, others will respond with second and so on. We have resolved all functions into n groups after application of the first value. Then, we apply the second input value of $k^m$ to every of n groups and every group is split further into $n$ subgroups. That is, after applying $i$ input values, we have resolved the functions into $n^i$ groups and, after applying all $k^m$ values, we resolved all functions into $n^{k^m}$ groups. So, we have $n^{k^m}$ different reactions. These are $n^{k^m}$ functions. We have no more input stimuli to resolve between the functions in the groups we have got. We say that functions within the remaining groups are identical.
This can be used for instance to compute the number of state-transition functions. Let's have n states. Then, function state_2 = next_state(state_1) which computes next state has n input values and n output values. This means that totally, we may have $n^n$ state-transition functions. I have not checked how much of them are revertible. An experiment program shows that amount of reversible functions is $n!$ of configurations.
The Factorial is because functions can be represented as lists of target states. For instance, [1, 1, 2, 2, 2] tells that first two states are mapped to state 1 and 3 other states to state 2.
This function is not reversible because there are multiple routes into states 1 and 2. But, we can spot here that irreversibility also means that there are no transitions into some states (particularly states 3,4 and 5 don't show up in [1,1,2,2,2]). This observation tells us that reversible functions must contain all $n$ states in their list representations, e.g. [1,4,3,5,2], i.e. reversible function lists are permutations of [1,2,..., n]. There is $n!$ of them.
$f(a_1, a_2, .., a_m)$
which produces one of n values at the output (range of the function has cardinality of $n$).
At first (assuming every argument $a_i$ can take the same range of values, $1..k$), there is $k^m$ combinations of input values (i.e. that is cardinality of function's domain). Now, what does it mean that functions are different? If they react identically, then they are not different. If functions are different, there must be a combination of inputs which differentiates between them: when that combination is applied as input, functions produce different values. Applying different inputs can differentiate between the functions! Let's do that.
We put all functions in one group initially and apply the first input value of $k^m$ combinations. Some functions will respond the first value of range, others will respond with second and so on. We have resolved all functions into n groups after application of the first value. Then, we apply the second input value of $k^m$ to every of n groups and every group is split further into $n$ subgroups. That is, after applying $i$ input values, we have resolved the functions into $n^i$ groups and, after applying all $k^m$ values, we resolved all functions into $n^{k^m}$ groups. So, we have $n^{k^m}$ different reactions. These are $n^{k^m}$ functions. We have no more input stimuli to resolve between the functions in the groups we have got. We say that functions within the remaining groups are identical.
 |
| Resolving the functions by probing their reaction on various inputs |
This can be used for instance to compute the number of state-transition functions. Let's have n states. Then, function state_2 = next_state(state_1) which computes next state has n input values and n output values. This means that totally, we may have $n^n$ state-transition functions. I have not checked how much of them are revertible. An experiment program shows that amount of reversible functions is $n!$ of configurations.
The Factorial is because functions can be represented as lists of target states. For instance, [1, 1, 2, 2, 2] tells that first two states are mapped to state 1 and 3 other states to state 2.
No comments:
Post a Comment