Bitácora · Lógica · Ensayo

El primer símbolo ya dice qué forma tiene

Cinco formas y cuatro primeros símbolos posibles: sólo el paréntesis deja dos caminos, y uno solo de sus símbolos de adentro está a profundidad uno.

En Un corte equivocado rompe las dos piezas quedó que el separador bueno de una palabra es uno solo, y que cualquier otro rompe las dos mitades. Falta la pregunta práctica: cómo se lo encuentra sin probar. En las fórmulas, la respuesta empieza antes de buscar nada, en el primer símbolo.

Una fórmula de tipo τ es una palabra armada por niveles a partir de las atómicas, y el Teorema 7 de la Guía 9 (pág. 12) dice que cada una tiene una y sólo una de cinco formas: las dos atómicas, $(t \equiv s)$ y $r (t_{1}, \dots, t_{n})$ , con $t$ , $s$ y los $t_{i}$ términos; $(φ_{1} η φ_{2})$ , con $η$ uno de los nexos $\land$ , $\lor$ , $\to$ , $\leftrightarrow$ ; $\neg φ$ ; y $Q v φ$ , con $Q$ un cuantificador y $v$ una variable. La definición entera y su lectura única están en Fórmulas de tipo τ y su lectura única.

Cuatro primeros símbolos para cinco formas

Puestas en fila, con el símbolo con que empieza cada una:

Forma	Primer símbolo
(1) $(t \equiv s)$	$($
(2) $r (t_{1}, \dots, t_{n})$	el primero del nombre $r$
(3) $(φ_{1} η φ_{2})$	$($
(4) $\neg φ$	$\neg$
(5) $Q v φ$	$\forall$ o $\exists$

Los nombres de un tipo no pueden usar los cuantificadores, $\neg$ , los nexos, los paréntesis, la coma ni $\equiv$ : son símbolos prohibidos en la definición de tipo. Así que el primer símbolo de un nombre de relación nunca es $($ , $\neg$ , $\forall$ ni $\exists$ , y las filas (2), (4) y (5) no se confunden con ninguna otra. Es lo que pregunta el Ejercicio 14(b), pág. 11: el primer símbolo de una fórmula es el primero de un nombre de relación, o es $\forall$ , $\exists$ , $\neg$ o $($ .

Y cada uno de esos, salvo el último, ya dice cómo sigue la lectura. Con $\neg$ no hay nada que pensar: lo que viene después es $φ$ . Con $\forall$ o $\exists$ viene una variable, y dónde termina también está decidido: en el primer numeral negrita, porque cada variable tiene uno solo y lo tiene al final. Con el primer símbolo de un nombre de relación, el nombre es el tramo hasta el primer $($ —los nombres no tienen paréntesis—, su aridad dice cuántos argumentos esperar, y separarlos ya es lectura de términos.

El $($ es la única fila con dos formas adentro: puede ser $(t \equiv s)$ o $(φ_{1} η φ_{2})$ . Ahí el primer símbolo se queda corto, y hace falta mirar un símbolo más. Cuál, lo dice la profundidad.

El único símbolo de profundidad uno

La profundidad de la posición $i$ de una palabra es la cantidad de $($ menos la cantidad de $)$ en su tramo inicial de longitud $i$ . En una palabra que empieza con $($ , los símbolos de profundidad uno son los que están adentro del paréntesis de afuera y de ningún otro. Y el hecho que resuelve el $($ es éste: si la palabra es una fórmula, entre los símbolos de profundidad uno hay exactamente un $\equiv$ o un nexo, y es el principal.

Un ejemplo de la pág. 10, del tipo de los reticulados con un orden:

((i (X 1, X 2) \equiv 0) \land (s (X 1, X 2) \equiv 1))

Tiene tres candidatos. El $\equiv$ de la posición 11 está a profundidad dos, el $\land$ de la 14 a profundidad uno y el $\equiv$ de la 24 a profundidad dos. El $\land$ es el principal, y las dos piezas son $(i (X 1, X 2) \equiv 0)$ y $(s (X 1, X 2) \equiv 1)$ .

Que siempre haya uno solo sale de dos hechos, los dos por inducción en la construcción. El primero es sobre los términos: un término no tiene ningún $\equiv$ ni ningún nexo —ni las variables ni los nombres los usan—, tiene tantos $($ como $)$ , y en ningún tramo inicial cierra más de lo que abrió. El segundo es sobre las fórmulas: también cierran todo lo que abren, y en una fórmula, todo $\equiv$ y todo nexo está adentro de algún par de paréntesis de ella misma. Las atómicas $r (t_{1}, \dots, t_{n})$ no tienen ninguno; en $(t \equiv s)$ el $\equiv$ queda adentro del par de afuera; en $(φ_{1} η φ_{2})$ el $η$ también, y los de $φ_{1}$ y $φ_{2}$ quedan adentro de los suyos y además del de afuera; $\neg$ y $Q v$ no agregan paréntesis, así que no cambian nada.

Con eso, la cuenta se hace sola. En $(t \equiv s)$ , el único $\equiv$ o nexo de toda la palabra es el $\equiv$ , porque $t$ y $s$ no tienen ninguno. En $(φ_{1} η φ_{2})$ , un $\equiv$ o un nexo de $φ_{1}$ está a profundidad uno —el paréntesis de afuera— más su profundidad dentro de $φ_{1}$ , que es por lo menos uno: queda a dos o más. Como $φ_{1}$ cierra todo lo que abre, el $η$ vuelve a estar a profundidad uno, y con $φ_{2}$ pasa lo mismo que con $φ_{1}$ . Lo que hay adentro de $t$ , $s$ , $φ_{1}$ y $φ_{2}$ está entre paréntesis o no tiene esos símbolos.

Lo que no sirve es tomar el primer nexo que aparece de izquierda a derecha, ni el último. En el ejemplo de arriba el primer candidato es un $\equiv$ que está adentro de la pieza izquierda, y elegirlo como principal es exactamente el corte equivocado del ensayo anterior.

La palabra con la que arranca es la (c) del Ejercicio 15, pág. 11. Tiene tres $($ y tres $)$ , empieza con un cuantificador y termina en $)$ : los controles rápidos no la delatan. Los primeros cuatro pasos salen bien. El $\exists$ se lleva la variable $X 3$ ; en lo que queda, el único $\equiv$ o nexo de profundidad uno es la $\to$ de la posición 13; $r (X 3, X 4)$ se lee entera; y el $\neg$ deja $(X 4 \equiv 0) \forall X 4$ . Recién en el quinto paso aparece el problema: esa pieza empieza con $($ , así que su forma exige terminar en $)$ , y termina en el negrita de $X 4$ .

La (a) del mismo ejercicio se corta por la razón contraria. Tiene seis $($ y seis $)$ , pero después del $\neg$ no hay, adentro del paréntesis de afuera, ningún $\equiv$ ni nexo de profundidad uno: el $\land$ está a profundidad dos, y el $\equiv$ del final también. Y las dos mitades del Ejercicio 13(a) —el corte por el primer $\land$ de $(((X 1 \equiv X 2) \land (X 1 \equiv X 1)) \land (X 2 \equiv X 2))$ — no pasan del primer paso: una no cierra sus paréntesis y la otra cierra uno antes de tiempo.

Lo medido

Esto no está en la guía. El universo: todas las fórmulas del tipo del Ejercicio 15, $({0, 1}, {+}, {r}, {(+, 2), (r, 2)})$ , que usan sólo las variables $X 1$ y $X 2$ , con los cuatro nexos, $\neg$ , y $\forall$ y $\exists$ sobre esas dos variables, y que tienen a lo sumo 18 símbolos. Se arman por construcción, desde las atómicas y sin leer ninguna palabra, así que de cada una se sabe de antemano qué forma tiene y dónde puso la construcción el símbolo principal. Son 235 264, y las 235 264 palabras son distintas: ninguna sale de dos construcciones, que es la lectura única vista desde el otro lado.

Primer símbolo	Formas que aparecen	Fórmulas
$($	$(t \equiv s)$ , y $(φ_{1} η φ_{2})$ con los cuatro nexos	54 592
$r$	$r (t_{1}, t_{2})$	1024
$\neg$	$\neg φ$	101 440
$\forall$	$\forall v φ$	39 104
$\exists$	$\exists v φ$	39 104

Cuatro de las cinco filas tienen una sola forma: ahí el primer símbolo decide solo, en todos los casos. De las 54 592 que empiezan con $($ , 1344 son $(t \equiv s)$ y 53 248 son $(φ_{1} η φ_{2})$ , y las 54 592 tienen exactamente un $\equiv$ o nexo de profundidad uno, en la posición donde la construcción puso el principal.

El control va al lado. 49 152 de esas 54 592, nueve de cada diez, tienen más de un $\equiv$ o nexo en total, así que «el único» sin la profundidad no existe. Tomar el primero de izquierda a derecha da el principal equivocado en 38 400, el 70 %; tomar el último, en otras tantas. Y leídas de afuera hacia adentro, las 235 264 dan fórmula, cada una con la forma con que se la armó.

Un procedimiento que siempre termina

Leer así no es buscar: en ningún momento se prueba un corte y se vuelve atrás. Cada paso mira un símbolo, a lo sumo recorre la pieza una vez para medir profundidades, y entrega piezas estrictamente más cortas; con los términos pasa lo mismo, por la lectura única de términos. Como la palabra tiene una cantidad finita de símbolos, la lectura termina, y termina de una de dos maneras: con todas las piezas leídas, o en un paso donde la forma que exige el primer símbolo no se cumple. En el primer caso la palabra es una fórmula; en el segundo no lo es, porque por el Teorema 7 una fórmula que empieza con ese símbolo sólo podía tener esa forma.

De paso, eso explica tanto paréntesis. $(φ_{1} \land φ_{2})$ se escribe con el par de afuera porque ese par es lo que pone al $\land$ a profundidad uno y a los nexos de $φ_{1}$ y $φ_{2}$ más abajo. $\neg$ y $Q v$ no lo necesitan: van adelante, y el primer símbolo ya los encuentra.

Y es lo que la guía deja para meditar en la pág. 14. Si $C$ , $F$ y $R$ son finitos —o, más en general, efectivamente computables, igual que la aridad $a$ —, el conjunto $F^{τ}$ es $Σ_{τ}$ -efectivamente computable: en las palabras con que la pág. 9 lo dice para $T^{τ}$ , hay un procedimiento efectivo que decide, para cada palabra de $Σ_{τ}^{*}$ , si es una fórmula de tipo $τ$ . El procedimiento es éste. Del tipo sólo pide poder contestar si un tramo es un nombre de relación, de función o de constante, y con qué aridad; con los tres conjuntos finitos, eso es mirar una lista.