GEB: Cómo se escribe "b es un MIU-número" en TNT notación

Question

(NOTA: Esta pregunta requiere que el acceso a, y la familiaridad con el libro Gödel, Escher, Bach, por Douglas Hofstadter. Por desgracia, yo no soy capaz de hacer la pregunta totalmente autosuficiente. En cualquier caso, para una descripción del sistema MIU, ver aquí, y para uno de TNT, ver aquí.)

---

Esta pregunta se refiere a la p. 263 de la última edición Americana de Gödel, Escher, Bach.

En esa página, Hofstadter escribe (el énfasis es mío):

...He señalado en el Capítulo VIII que incluso un aritmética simple predicado como "b es una potencia de 10" es muy difícil de código en TNT de notación y el predicado "b es un MIU-número" es mucho más complicado que eso! Todavía se puede encontrar, ...

Hice hincapié en la última frase anterior, porque, en mi opinión, el libro de toda la interpretación de la prueba de Gödel (podría decirse que su eje central) recae sobre ella. Si esa afirmación debe ser tomada en la fe, entonces el libro de toda la prueba debe ser tomado en la fe.

Es terriblemente decepcionante que en un libro de este tamaño, que hace que tales demandas de sus lectores, y que está lleno de enormes ilustraciones (tales como la secuencia completa de un genoma viral, en la p. 176), el autor optó por no proporcionar explícitamente tal crucial de la exhibición en el argumento. Sí, sé que el resultado de la cadena TNT sería enorme (incluso antes de la sustitución de SSSSSSSSSSSSSSSSSSSSSSSSSSSSSS0 para cada ocurrencia de b), y básicamente incomprensible (aunque dudo que iba a ser más que el genoma aludido anteriormente), pero es una parte importante de la evidencia de que tener su existencia en la fe es, como he dicho, terriblemente decepcionante.

Por lo tanto, como este tema título lo dice, estoy buscando la traducción de el predicado "b es un MIU-número" a TNT notación.

He buscado en línea para esta traducción sin éxito.

Como ya he mencionado, me doy cuenta de que la traducción de este predicado a TNT notación podría resultar en una enorme cadena, quizás inmanejable.

En ese caso, lo mejor sería un andamio escrito en un lenguaje formal L más expresivo (por lo tanto más breves) de TNT, pero a partir de la cual se podría traducir en TNT a través de un sencillo proceso de expansión (es decir, la sustitución de la sucinta L expresiones por completo soplado TNT expresiones).

Por ejemplo, un lenguaje L puede incluir un símbolo de $\leq$ que podría ser traducido a "lax TNT" por la aplicación de la siguiente sustitución: $$a\leq b \to \exists c:(a+c)=b$$

...o "estricto TNT":

$$a\leq a^\prime \to \exists a^{\prime\prime}:(a+a^{\prime\prime})=a^\prime$$

Asimismo, L podría incluir un símbolo de $\lt$, que podría ser traducido a TNT con la sustitución:

$$a \lt b \to \mathbf{S}a \le b \;,$$

o

$$a \lt a^\prime \to \mathbf{S}a \le a^\prime\;.$$

El punto aquí es que la LHSs de arriba son considerablemente más breve que el correspondiente RHSs, y una expresión que contiene a la anterior puede ser traducida como "mecánicamente" a uno compuesto sólo de la validez de TNT a través de símbolos relativamente sencillo sustituciones. Por lo tanto, L puede ser pensado como TNT aumentada con un conjunto finito de "abreviaturas", como los ejemplificados por $\le$ $\lt$ por encima.

No es difícil ver que, con suficiente "abreviaturas" de este tipo, uno puede ser capaz de traducir el predicado "b es un MIU-número" a un L-cadena de longitud manejable, incluso si la correspondiente cadena TNT es un par de órdenes de magnitud más grande.

---

Para lo que vale, sé que el predicado "b es un MIU-número" es equivalente a la siguiente predicado:

b es un número que consta de $3$, seguido por $0$'s y $1$'s, donde el número de $n_1$ $1$'s satisface $n_1 \not \equiv 0 \pmod 3$.

(Ver esta respuesta por Eric Wofsey para una prueba interesante de esta equivalencia.)

Por lo tanto, para responder a esta pregunta, sería suficiente para traducir de esta alternativa, pero equivalente, predicado a TNT notación.

Answer 1

Una manera de hacer esto implica (como Eric Wofsey aludido) en la codificación de una secuencia dentro de un número. Una vez que podemos hacer esto, podemos definir un MIU-secuencia como una secuencia en la que el primer término es $31$, y cada término se obtiene del anterior por uno de los cuatro MIU reglas. A continuación, $b$ es un MIU-número de iff hay un MIU-secuencia que termina con $b$.

Hay una discusión de cómo se codifican las secuencias de aquí (y en otras cuestiones relacionadas en el sitio); voy a utilizar Hagen von Eitzen la codificación de allí.

Hagen von Eitzen presenta las siguientes abreviaturas:

$$\begin{align}a\le b&\equiv\exists c\colon (a+c)=b\\ a< b&\equiv Sa\le b\\ \operatorname{mod}(a,b,c)&\equiv \exists d\colon a=((b\cdot d)+c)\land c<b\\ \operatorname{seq}(a,b,e,c)&\equiv \operatorname{mod}(a,S(b\cdot Se),c)\\ \operatorname{pow}(a,b,c)&\equiv\exists x\exists y\colon\operatorname{seq}(x,y,0,S0)\land\operatorname{seq}(x,y,b,c)\land \\&\quad\forall k\forall z\colon((k<b\land \operatorname{seq}(x,y,k,z))\supset\operatorname{seq}(x,y,Sk,a\cdot z))\end{align}$$

Intuitivamente, $\operatorname{seq}(a,b,e,c)$ se supone que significa que el par de números de $a$ $b$ codificar una secuencia en la que $c$ $e$th término de la secuencia.

$\operatorname{pow}(a,b,c)$ se supone que significa eso $c=a^b$; esto no es parte de la secuencia de codificación, pero era relevante para la pregunta que hay y que será útil para la codificación de la MIU reglas. (Espero que excusa el uso de las variables de $k,x,z$ que no son parte de TNT; que, por supuesto, pueden ser considerados como abreviación $d',d'',d'''$ o algo así).

También queremos codificar el MIU reglas (voy a usar la $10$ como abreviación $SSSSSSSSSS0$, etc.): $$\begin{align} \operatorname{M1}(a,b) &\equiv \exists c: a = ((10 \cdot c)+1)\land b = (10\cdot a) \\\operatorname{M2}(a,b) &\equiv \exists c \exists d \exists e : a=((3\cdot e)+c)\land \operatorname{pow}(10,d,e) \land c<e \land b = ((e \cdot a)+c) \\\operatorname{M3}(a,b) &\equiv \exists c \exists d \exists e \exists c': a = ((c' \cdot (1000 \cdot e))+(111 \cdot e)+c) \land \operatorname{pow}(10,d,e) \land c<e \land b = ((c' \cdot (10 \cdot e))+c) \\\operatorname{M4}(a,b) &\equiv \exists c \exists d \exists e \exists c': a = ((c' \cdot (100 \cdot e))+c) \land \operatorname{pow}(10,d,e) \land c<e \land b = ((c' \cdot e)+c) \end{align}$$

Intuitivamente, $\operatorname{M1}(a,b)$ dice $b$ se obtiene a partir de a $a$ por el primer MIU regla (de acuerdo a su numeración en el artículo de Wikipedia), etc.

Por último, afirmar que $b$ es un MIU-número, queremos afirmar que hay una secuencia codificada por un par de números tales que el primer término es $31$, el último término es $b$, y cada término se obtiene del anterior por una de las cuatro reglas. Podemos modelo de Hagen von Eitzen $\operatorname{pow}$ frase, el uso de $e$ para la longitud de la secuencia y $x,y$ para el par de codificación.

$$ \operatorname{MIUnumb}(b) \equiv \exists x \existe y \existe e : \operatorname{seq}(x,y,0,31) \de la tierra \operatorname{seq}(x,y,e,a, b) \de la tierra \forall d \forall \forall': d<e \de la tierra \operatorname{seq}(x,y,d,a) \de la tierra \operatorname{seq}(x,y,Sd,a')) \supset (\operatorname{M1}(a,a') \lor \operatorname{M2}(a,a') \lor \operatorname{M3}, (a, a') \lor \operatorname{M4}, (a, a')) $$

Answer 2

Como Y. Forman la respuesta, voy a hacer uso de Hagen von Eitzen la solución elegante para el poder-de-diez problema. Sin embargo, en lugar de seguir la definición real de MIU números, voy a usar el que citó como equivalente:

b es un número que consta de $3$, seguido por $0$'s y $1$'s, donde el número de $n_1$ $1$'s satisface $n_1 \not\equiv 0\pmod 3$.

Primero, vamos a comprobar si el número de $b$ se compone únicamente de ceros y unos, aparte de que el primer dígito que debe ser igual a $3$. El uso de la "$\operatorname{pow}$", "$<$", "$10$" y "$3$" abreviaturas de la que se hace referencia post, podemos expresarlo de la siguiente forma:

$$(\forall e)(\forall m)(\operatorname{pow}(10,e,m)\implies (\exists q)(\exists r)(b = q\times m + r \land (r<m)\land (q=0\lor q=3\lor (\exists q')(q = 10\times Sq' \lor q=S(10\times Sq')))))$$

En esta expresión, $e$ es utilizado como exponente de $10$ utilizado para la comprobación de cada uno de los dígitos de $b$ por separado, con $m=10^e$. Dividiendo $b$ $m$ rendimientos $q$(uotient) y $r$(emainder), donde el cociente puede ser igual a $3$ (el primer dígito de $b$), cero (si es que estamos buscando a los "dígitos", precediendo a la primera) o debe ser mayor o igual a$10$, y el último dígito debe ser $0$ o $1$.

Este "casi" funciona; sólo falla por $b=0$ donde todos los dígitos caer en la $q=0$ categoría. Podríamos solucionar esto simplemente mediante la adición de una condición de $b\not =0$, pero como resulta que, va a ser resuelto de forma gratuita por la otra propiedad: La condición de $n_1\not\equiv 0\pmod 3$.

Este puede ser revisado en forma muy compacta: $$\neg(\exists k) b=3\times k$$

Funciona porque un número es divisible por $3$ si y sólo si su digital suma es divisible por $3$ y el digital suma de $b$$(3+n_1)$. Por lo tanto, $b$ sí está prohibido de ser un múltiplo de $3$; que también resuelve el $b=0$ de los casos.

La combinación de las dos fórmulas anteriores y la sustitución de las definiciones de $\operatorname{pow}$, $<$, las constantes y cambiar el nombre de las variables daría la deseada predicado expresado en puro TNT... pero no sería una bonita vista. Sin embargo, debido a la utilización de sólo una ocurrencia de $\operatorname{pow}$, esta expresión debe ser considerablemente menor que la que se construye directamente a partir de la definición de MIU.