4 Suponga que tenemos algunas proteínas, y que cada proteína es una secuencia de 7 "AMINO-ACIDS" $A,\ B,\ C,\ H,\ F,\ N$ . Por ejemplo, $AFHNNNHAFFC$ es una proteína. Hay algunos pasos en los que, en cada paso, un aminoácido cambiará a otro. Por ejemplo, con el paso $NA\rightarrow N$ la proteína $BANANA$ cambiará a $BANNA$ ( "en persa significa obrero"). Tenemos un conjunto de pasos permitidos con los cuales cada proteína puede cambiar. Por ejemplo, con el conjunto de pasos: $\\ 1)\ AA\longrightarrow A\\ 2)\ AB\longrightarrow BA\\ 3)\ A\longrightarrow \mbox{null}$ La proteína $ABBAABA$ cambiará así: $\\ ABB\underline{AA}BA\\ \underline{AB}BABA\\ B\underline{AB}ABA\\ BB\underline{AA}BA\\ BB\underline{AB}A\\ BBB\underline{AA}\\ BBB\underline{A}\\ BBB$ Se ve que después de un número finito de pasos esta proteína terminará sus pasos. Un conjunto de pasos permitidos para el cual existe una proteína que puede tener infinitamente muchos pasos es peligroso. ¿Cuáles de los siguientes conjuntos permitidos son peligrosos? a) $NO\longrightarrow OONN$ b) $\left\{\begin{array}{c}HHCC\longrightarrow HCCH\\ CC\longrightarrow CH\end{array}\right.$ c) Diseñe un conjunto de pasos permitidos que cambie $\underbrace{AA\dots A}_{n}\longrightarrow\underbrace{BB\dots B}_{2^{n}}$ d) Diseñe un conjunto de pasos permitidos que cambie $\underbrace{A\dots A}_{n}\underbrace{B\dots B}_{m}\longrightarrow\underbrace{CC\dots C}_{mn}$ Se ve de $c$ y $d$ que podemos calcular las funciones $F(n)=2^{n}$ y $G(M,N)=mn$ con estos pasos. Encuentre otras funciones calculables con estos pasos. (Tiene una calificación adicional.) Omid