Rompecabezas y soluciones de Godel, Escher, Bach Typographical Number Theory (TNT)

Question

En el capítulo 8 de Godel, Escher, Bach por Douglas Hofstader, el lector tiene el desafío de traducir estas 2 declaraciones a TNT:

" b es una potencia de 2 "

y

" b es una potencia de 10 "

¿Son correctas las siguientes respuestas ?:

(Asumiendo '& # 8707;' significa 'existe un número'):

& # 8707; x: (x.x = b)

es decir " existe un número 'x' tal que x multiplicado x es igual a b "

Si eso es correcto, entonces el siguiente es igualmente trivial:

& # 8707; x: (x.x.x.x.x.x.x.x.x.x = b)

Estoy confundido porque el autor indica que son engañosos y que el segundo debería tardar horas en resolverse; ¡Debo haber perdido algo obvio aquí, pero no puedo verlo!

Answer 1

Sus expresiones son equivalentes a las declaraciones " b es un número cuadrado " y & "; b es la décima potencia de un número &"; respectivamente. Convirtiendo & Quot; potencia de & Quot; declaraciones en TNT es considerablemente más complicado.

Answer 2

En general, diría & "; b es una potencia de 2 &"; es equivalente a " cada divisor de b excepto 1 es un múltiplo de 2 " ;. Es decir:

& # 8704; x ((& # 8707; y (y * x = b & amp; & # 172; (x = S0))) & # 8594; < !> # 8707; z (SS0 * z = x))

EDITAR: Esto no funciona para 10 (gracias por los comentarios). Pero al menos funciona para todos los números primos. Lo siento. Creo que tienes que usar algún tipo de secuencias de codificación después de todo. Sugiero & Quot; G & # 246; Teoremas de incompletitud de del & Quot; por Raymond Smullyan, si desea un enfoque detallado y más general sobre esto.

O puede codificar Secuencias de números usando el Teorema del resto chino, y luego codificar definiciones recursivas, de modo que pueda definir Exponenciación. De hecho, así es básicamente cómo puede probar que la aritmética de Peano se está completando.

Prueba esto:

D(x,y)=∃a(a*x=y)
Prime(x)=¬x=1&∀yD(y,x)→y=x|y=1
a=b mod c = ∃k a=c*k+b

Entonces

∃y ∃k(
 ∀x(D(x,y)&Prime(x)→¬D(x*x,y)) &
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z<x→¬D(z,y))→(k=1 mod x)) &
 ∀x∀z(D(x,y)&Prime(x)&D(z,y)&Prime(z)&z<x&∀t(z<t<x→¬(Prime(t)&D(t,y)))→
  ∀a<x ∀c<z ((k=a mod x)&(k=c mod z)-> a=c*10))&
 ∀x(D(x,y)&Prime(x)&∀z(Prime(z)&z>x→¬D(z,y))→(b<x & (k=b mod x))))

debería indicar & "; b es Potencia de 10 &"; en realidad dice & "; hay un número yy un número k tal que y es producto de primos distintos, y la secuencia codificada por k a través de estos primos comienza con 1, tiene la propiedad de que el siguiente elemento c de a es 10 * a, y termina con b "

Answer 3

Hay una solución para " b es una potencia de 10 " problema detrás del botón de spoiler en la publicación del científico escéptico aquí . Depende del teorema del resto chino de la teoría de números y de la existencia de secuencias aritméticas arbitrariamente largas de números primos. Como indicó Hofstadter, no es fácil encontrarlo, incluso si conoce los teoremas apropiados.

Answer 4

que tal:

& # 8704; x: & # 8704; y: (SSx & # 8729; y = b & # 8594; & # 8707; z: z & # 8729 ; SS0 = SSx)

(en inglés: cualquier factor de b que sea & # 8805; 2 debe ser divisible por sí mismo por 2; literalmente: para todos los números naturales x e y, si (2 + x) * y = b, esto implica que hay un número natural z tal que z * 2 = (2 + x).)

No estoy 100% seguro de que esto esté permitido en la sintaxis de TNT y cálculo proposicional , ha pasado un tiempo desde que examiné GEB.

(edit: para el problema b = 2 ⁿ al menos; puedo ver por qué el 10 ⁿ sería más difícil ya que 10 no es primo. Pero 11 < sup> n sería lo mismo, excepto reemplazar el término " SS0 " con " SSSSSSSSSSS0 " ;.)

Answer 5

Al expresar & "; b es una potencia de 10 &"; en realidad no necesita el Teorema del resto chino y / o la codificación de secuencias finitas. Alternativamente, puede trabajar de la siguiente manera (usamos los símbolos habituales como |, & Gt ;, c-d, como accesos directos para fórmulas / términos con significado obvio):

1. Para un número primo p, denotemos EXP (p, a) alguna fórmula en TNT que dice que " p es un primo y a es una potencia de p " ;. Ya sabemos cómo construir uno. (Por razones técnicas, no consideramos que S0 sea una potencia de p, entonces ~ EXP (p, S0)).

2. Si p es primo, definimos EXP _p (c, a) & # 8790; & # 10216; EXP (p, a) & # 8743; (c-1) | (a-1) & # 10217 ;. Aquí, el símbolo | es un atajo para " divide " que se puede definir fácilmente en TNT usando un cuantificador y multiplicación existencial; lo mismo vale para c-1 (a-1, resp.) que significa & "; d de tal manera que Sd = c &"; (Sd = a, resp.).
   Si EXP (p, c) se cumple (es decir, c es una potencia de p), la fórmula EXP _p (c, a) dice que & Quot; a es una potencia de c " desde un & # 8801; 1 (mod c-1) entonces.

3. Al tener una propiedad P de números (es decir, enteros no negativos), hay una manera de referirse, en TNT, al número más pequeño con esta propiedad: & # 10216; P (a) & # 8743; & # 8704; c: & # 10216; a & Gt; c & # 8594; ~ P (a) & # 10217; & # 10217 ;.

4. Podemos establecer la fórmula que expresa & "; b es una potencia de 10 &"; (para una mejor legibilidad, omitimos los símbolos & # 10216; y & # 10217 ;, y escribimos 2 y 5 en lugar de SS0 y SSSSS0):
   & # 8707; a: & # 8707; c: & # 8707; d: (EXP (2, a) & # 8743; EXP (5, c) & # 8743; EXP (5, d) & # 8743; d & Gt; b & # 8743; a & # 8901; c = b & # 8743; & # 8704; e: (e > 5 & # 8743; e | c & # 8743; EXP ₅ (e, c) & # 8594; ~ EXP ₅ (e, d)) & # 8743; & # 8704; e: (" e es el más pequeño de modo que EXP ₅ (c, e) & # 8743; EXP ₅ (d, e) & Quot; & # 8594; (d-2) | (ea))).

Explicación: Escribimos b = a & # 8901; c = 2 ^x & # 8901; 5 ^y ( x, y > 0) y elija d = 5 ^z > b de tal manera que z e y sean coprimos (por ejemplo, z puede ser primo). Entonces & Quot; el más pequeño e ... & Quot; es igual a (5 ^z ) ^y = d ^y & # 8801; 2 ^y (mod d-2), y (d-2) | (ea) implica a = 2 ^x = e mod (d-2) = 2 ^y (tenemos 'd-2 > 2 ^y ' y 'd-2 > a', también), y entonces x = y.

Observación: Este enfoque se puede adaptar fácilmente para definir " b es una potencia de n " para cualquier número n con una descomposición fija a ₁ a ₂ ... a _k , donde cada a _i es una potencia de un p _i y p _i = p _j & # 8594; i = j.

Answer 6

Esto es lo que se me ocurrió:

& # 8704; c: & # 8707; d: < (c * d = b) & # 8594; < (c = SO) v # 8707; e: (d = e * SSO) & Gt; & Gt;

Que se traduce en:

Para todos los números c, existe un número d, de modo que si c multiplicado por d es igual a b, entonces c es 1 o existe un número e tal que d es igual a e multiplicado por 2.

O

Para todos los números c, existe un número d, de modo que si b es un factor de cyd entonces c es 1 o d es un factor de 2

O

Si el producto de dos números es b, entonces uno de ellos es 1 o uno de ellos es divisible por 2

O

Todos los divisores de b son 1 o son divisibles por 2

O

b es una potencia de 2

Answer 7

Creo que la mayoría de los anteriores solo han demostrado que b debe ser un múltiplo de 4. ¿Qué tal esto: & # 8707; b: & # 8704; c: < < & # 8704; e: (c & # 8729; e) = b & amp; ~ & # 8707; c ': & # 8707; c' ':( ssc' & # 8729; ssc '') = c & Gt; & # 8594; c = 2 >

No creo que el formato sea perfecto, pero dice:

Existe b, de modo que para todo c, si c es un factor de byc es primo, entonces c es igual a 2.

Answer 8

Esto es lo que se me ocurrió para la declaración & "; b es una potencia de 2 &";

& # 8707; b: & # 8704; a: ~ & # 8707; c: ((a * ss0) + sss0) * c = b

Creo que esto dice " Existe un número b, tal que para todos los números a, no existe un número c tal que (a * 2) + 3 (en otras palabras, un número impar mayor que 2) multiplicado por c, te da b. " Entonces, si b existe, y no puede ser cero, y no tiene divisores impares mayores que 2, ¿entonces b no sería necesariamente 1, 2 u otra potencia de 2?

Answer 9

Para la expresión abierta que significa que b es una potencia de 2, tengo ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Esto efectivamente dice que para todo a, S (Sa & # 8729; SS0) no es un factor de b. Pero en términos normales, S (Sa & # 8729; SS0) es 1 + ((a + 1) * 2) o 3 + 2a. Ahora podemos reformular el enunciado como & Quot; ningún número impar que sea al menos 3 es un factor de b & Quot ;. Esto es cierto si y solo si b es una potencia de 2.

Todavía estoy trabajando en el problema b es una potencia de 10.

Answer 10

mi solución para b es una potencia de dos es: & # 8704; x: & # 8707; y x.y = b (isprime (x) = & Gt; x = SS0)

isprime () no debería ser difícil de escribir.