Diremos que una cadena de signos \( f \) de \( \mathcal L_{\rm arp} \) es un funtor de rango \( n \) (o un funtor \( n \)-ádico) si existen una sucesión \( f_1,\ldots, f_r \) de cadenas de signos y una sucesión \( n_1,\ldots, n_r \) de números naturales de modo que \( f\equiv f_r \), \( n = n_r \) y, para cada índice \( i \), se da uno de los casos siguientes:
- \( f_i\equiv S \) y \( n_i = 1 \),
- \( f_i\equiv c \) y \( n_i = 1 \),
- Existe \( 1\leq k\leq n_i \) tal que \( f_i\equiv p^{n_i}_k \),
- Existen índices \( j, j_1,\ldots, j_m<i \) tales que \( n_j=m \), \( n_{j_k}= n_i \), para todo \( k \) y
\( f_i \equiv \kappa(f_j,f_{j_1},\ldots, f_{j_m})\equiv \kappa f_jf_{j_1}\cdots f_{j_m} \),
- Existen \( j, k<i \) tales que \( n_i = n_j+1 \), \( n_k = n_j+2 \) y
\( f_i \equiv \rho(f_j, f_k)\equiv \rho f_jf_k \).
Aquí \( n_i = n_j+1 \) sólo significa que \( n_i \) es el siguiente de \( n_j \), mientras que \( n_k = n_j+2 \) sólo significa que \( n_k \) es el siguiente del siguiente de \( n_j \), y todo esto lo puede entender un lector que no sepa sumar.
Esta definición se nota que la has dado con sumo cuidado,
no sólo para que sea coherente en sí misma,
sino para facilitar las demostraciones que aparecen en el mismo post más abajo.
Es todo bastante obvio tras "masticarse" esta definición.
A pesar de los aspectos positivos que le veo,
aún así puede tener algún rol dar una definición alternativa,
por ejemplo de manera recursiva,
al menos para comparar una cosa con la otra.
Creo que me marea el uso de tantos índices, los cuales son números naturales que están fuera del lenguaje \(L_{arp}\), y me pregunto por qué no se usa exclusivamente el lenguaje \(L_{arp}\) para definir los funtores.
Un
numeral (positivo) sería la cadena \(S0\)
ó bien \(S\) seguido de (yuxtapuesto a) una cadena
que ya se determinó previamente que era un numeral.
Una
proyección sería el signo \(p\) seguido de un numeral \(\mathbf k\),
que tendría una cantidad \(k\) de signos "\(S\)",
seguido de otro numeral \(\mathbf n\), tal que \(\mathbf n\) es igual a \(\mathbf k\),
o bien se obtiene de \(\mathbf k\) yuxtaponiendo varias \(S\) a la izquierda.
Si se agregan \(h\geq0\) de estas "\(S\)"s a la izquierda,
sería \(n=k+h\geq k\),
donde \(n\) es la cantidad de "\(S\)"s del numeral \(\mathbf n\),
que es lo que se requiere.
Establecemos que el orden de \(S\) (como funtor) es 1,
el orden \(c\) es 1,
y el orden de \(p \mathbf k\mathbf n\) es \(n\).
Para el caso de las composiciones,
si tenemos un funtor \(h\) de orden \(m\),
y \(m\) funtores \(g_1,\ldots,g_m\) de orden \(n\),
entonces \(\kappa h g_1\ldots g_m\) será un funtor, con orden \(n\).
Si \(g\) es funtor de orden \(n\), \(h\) funtor de orden \(n+2\),
entonces \(\rho gh\) es funtor de orden \(n+1\).
Tras estas declaraciones (y aclarando que no hay más funtores que los obtenidos por esas reglas), se tendría que poder reconstruir toda la familia de funtores del hilo original.
Me resulta más complicado de probar,
o sea que el precio de eliminar los sub-sub-índices que me disgustan tanto
es que las pruebas de que todo funciona bien son más rebuscadas.
_________________
Se me ocurre una formulación alternativa, en la cual no haya necesidad ni de tantos índices ni de tantas comprobaciones.
Entre los índices incluiría al cero, y las proyecciones y los funtores ya no tendrían un orden dado en forma explícita, sino sólo de forma implícita.
Para empezar, todas las funciones primitivas tendrían infinitas variables,
aunque sólo se usarían una cantidad finita cada vez:
\(S(x_1,x_2,\ldots) = x_1+1\).
\(c_0(x_1,x_2,\ldots) = 0\).
\[p_k(x_1,x_2,\ldots) = \begin{cases}x_k;\qquad& k\leq n\\ 0;&k>n\end{cases}\]
En particular, \(p_0 =c_0\).
Notar que ya no necesitamos los superíndices \(n\) para las proyecciones.
La información de la \(n\)-aridad se pierde, pero no sé si es tan grave esto.
En particular, me resulta más natural pensar que la constante \(c_0\) es,
en realidad, una función
0-ádica.
Si \(H,G_1,\ldots,G_m\) son funciones de \(\mathbb N^\infty\) en \(\mathbb N\),
entonces su composición sería:
\(F=H\circ (G_1,\ldots,G_m)\):
\[F(x_1,x_2,\ldots) = H(G_1(x_1,x_2,\ldots), \ldots,G_m(x_1,x_2,\ldots),0,0,\ldots).\]
Si \(G,H\), son funciones de \(\mathbb N^\infty\) en \(\mathbb N\), entonces,
se define la \(n\)-ésima función recursiva \(F_n\), asociada a \(G\) y \(H\),
con \(n\geq 0\) así:
\[F_n(x_1,x_2,\ldots,x_n,0,0,0,\ldots) = G(x_1,x_2,\ldots,x_n,0,0,\ldots).\]
\[F_n(x_1,x_2,\ldots,x_n,k+1,0,0,\ldots = H(x_1,x_2,\ldots,x_n,k,F_n(x_1,x_2,\ldots,x_n,k,0,0,\ldots),0,0,\ldots).\]
_____________
Luego, para los funtores, uno sí necesita una cantidad finita de argumentos,
pero se puede hacer allí mismo el truco:
Un funtor comenzaría con las signos \("s","p","\kappa","\rho"\)
(estoy agregando un signo nuevo "\(s\)", porque me incomoda que se use "\(S\)" para el funtor sucesor, y también "\(S\)" para los numerales).
Un funtor "sucesor" sería \(s\).
Un funtor "proyección" sería \(pN_1\ldots N_k\),
donde \(N_j\) son numerales ("\(0\)", "\(S0\)", "\(SS0\)", etc.).
La cantidad \(k\) de numerales sería arbitraria, incluso 0.
Si \(k=0\), podríamos convenir que \(p\) denote el funtor
constante cero \(c\).
Con estas convenciones, no haría falta el signo "\(c\)".
Si \(k=1\), estaríamos antes las proyecciones tal como en el hilo principal.
Y si \(k>1\), entonces los índices \(N_2,\ldots,N_k\) tan simplemente se ignorarán.
A continuación, dados \(k+1\) funtores \(h,g_1,\ldots,g_k\),
la cadena \(\kappa \mathbf k h g_1\ldots g_k\) sería un
funtor composiciónque espera \(k\) "argumentos", donde el numeral \(\mathbf k\)
se encarga de anticipar esta información.
Esto tendría sentido incluso si \(k=0\).
De modo que si hubiesen más argumentos que los esperados,
o bien serían parte de un argumento de un funtor composición
que aparece anunciado previamente en la cadena,
o bien habría que ignorar su contenido.
En el caso de que falten argumentos (cosa que podría suceder al final de una cadena),
se tomarían implícitamente como cero ("\(c\)").
Si el numeral \(\mathbf k\) no le sigue a \(\kappa\),
entonces asumir que estamos ante un caso especial.
Por ejemplo, podría asumirse que \(k\) representa la constante \(c\),
o bien que \(k\) es el funtor "siguiente", eliminando así el signo "\(s\)" del alfabeto.
Dados funtores \(g,h\), el \(n\)-ésimo funtor recursión de \(g,h\) sería la cadena:
\(\rho\mathbf n gh\).
Si hubiese más funtores a la derecha, sería aceptable,
pero a la hora de identificar funtores con funciones, se ignorarían:
\(\rho\mathbf n gh h_2,\ldots,h_k.\)
Si faltaran \(h\) y/o \(g\) (esto ocurriría al final de algunas cadenas),
se tomarían implícitamente como cero.
Con estas convenciones, la intención es que sea sencillo verificar si una cadena es válida o no, pues casi cualquier cosa sería válida, y hacer la semántica de ARP más directa.
No me he puesto en verificar los detalles, y seguramente si lo terminara,
me quedaría cualquier otra cosa
(mi intención es que toda cadena de signos de \( \mathcal L_{arp}\) sea válida,
y cargarle todo el trabajo a la semántica de ARP).
Por otra parte, no sé si todavía esto se podría llamar ARP,
pues cuando menos, se pierde bastante de la intuición de la formulación original.
