Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the sets
$K_1=\{\{a_0,b_1\},\{a_1\},\{b_0\}\}$.
$K_2=\{\{c_1,c_0,d_0,e_1\},\{d_1\},\{e_0\}\}$
$K_3=\{\{f_0,f_2,g_0,h_1\},\{f_1,f_3,g_2,h_3\},\{b_1\},\{b_3\},\{c_0\},\{c_2\}\}$

Every item of the form $letter_{digit}$ is a possible state for the system $K_i$. If two items are in the same set, say for $K_1$, $\{a_0,b_1\}$, then a transition between them is possible $(a_0\leftrightarrow b_1)$.

Using any finite amount of $K_i$'s, and an allowed operation of making sets consisting of two or more letters like this: $\{{a,b,f\}}$, which means a transition between $a_x,b_y,f_z$ is allowed for any $x,y,z$.

If we have two or more of one $K_i$, these are assigned different letters (ie none of a,b,c.. is used for two different $K_i$). When we transition from a state say $a_z$ in $K_j$, to that of another $b_y$ in $K_i$, and eventually return to a letter in $K_j$, then the digit $z$ is preserved of $K_i$ (it doesnt change state by itself).

A letter which is not identified with any other (by the method ${a,b,f}$ in above example), is called loose, initially all letters are loose (disconnected).

Is it possible to construct a composition using above rules to create a system acting like $X$ below, i.e. in total there is $3$ loose letters, every $K_i$ is assigned an initial state, and the resulting thing must follow the transition rules given by $X$:

$X=\{\{i_0,j_1\},\{i_1,k_0\},\{j_0\},\{k_1\}\}$

This thing has only two states, $0$ and $1$, this just means that the states of the $K_i$'s it is composed of, should only have two outcomes on the possible transitions between the loose letters (the internal state must be cyclic with period 2t for some t).

The state of this thing is then given completely by the state of each K_i (a single number for each), and exactly one letter in total. And is there a general method to decide given any $K_i$'s and $X$ to decide if $X$ is composable of some number of the $K_i$'s ?

Is there some finite atomic set of $K_i$'s by which any possible $X$ is composable?

Is there a more natural framework in which this question can be reformulated and answered?

share|improve this question
3  
This looks like the result of too much abstraction applied to a real-world problem. Can you tell us what motivated this question? –  Rahul Jan 12 '12 at 23:21

2 Answers 2

I think it would help if you could reformulate your question, as it is not very clear to me what's the actual system you want to work on.

Given the sets K1=... K2=... K3 =...

Do you want to work on these specific sets, or are they just examples (which seems to be the case, considering the following question)? In this case, what's the global system? Do you get something like an alphabet $A$, a set of states $\Sigma = A \times \mathbb{N}$, and each $K_i$ belongs to the set $\mathcal{K} \subseteq 2^\Sigma$ ?

Every item of the form $letter_{digit}$ is a possible state for the system $K_i$. If two items are in the same set, say for K1, {a0,b1}, then a transition between them is possible (a0↔b1).

Given a set $K_i$, is there a relation between $i$ and the indexes of the states in $K_i$? For instance, for any $X \in K_i$, if $(a, j) \in X$ then $j \leq i$? (as it seems to be the case on the examples).

Using any finite amount of $K_i$'s, and an allowed operation of making sets consisting of two or more letters like this: {a,b,f}, which means a transition between $a_x$, $b_y$, $f_z$ is allowed for any $x,y,z$.

I think there is a verb missing in this sentence, but do you mean that an allowed operation is just a subset of $A$ ?

If we have two or more of one Ki, these are assigned different letters (ie none of a,b,c.. is used for two different Ki).

It doesn't seem to be the case in your examples, for instance $b_1$ is used both in $K_1$ and $K_3$.

A letter which is not identified with any other (by the method a,b,f in above example), is called loose, initially all letters are loose (disconnected).

So, if I understand correctly, you consider two things: a set $S = \{K_1, K_2, \cdots, K_n\} \subseteq \mathcal{K}$ and a method $m = {a, b, \cdots, f} \subseteq A$? And a letter $a$ is loose in $(S, m)$ if and only there exists $K_i \in S$, such that there exists $X \in K_i$ such that there exists j such that $(a, j) \in X$ and $a \not \in m$ ?

Then, I'm not sure what you mean by "initially". Do that mean that initially the method $m$ is empty?

Is it possible to construct a composition using above rules to create a system acting like X below, i.e. in total there is 3 loose letters, every Ki is assigned an initial state, and the resulting thing must follow the transition rules given by X: X={{i0,j1},{i1,k0},{j0},{k1}}

To construct from what? What's a composition? What's an initial state?

Is there a more natural framework in which this question can be reformulated and answered?

At first glance, I think Set Theory should be enough to express what you want, but you would need to be more formal, to define precisely the structures you are manipulating. I'd be glad to think more about your problem if you could come up with a clearer description of it.

share|improve this answer

If you can make three systems ("K_i") that are analogous to the AND, OR, NOT gate, then I think you can ´compose´ a system corresponding to any computable function, because your system will be turing complete.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.