Godel, Escher, Bach tipográficos Teoria dos Números (TNT) puzzles e soluções

StackOverflow https://stackoverflow.com/questions/644569

  •  22-07-2019
  •  | 
  •  

Pergunta

No capítulo 8 de Godel, Escher, Bach por Douglas Hofstader, o leitor é desafiado a traduzir essas 2 instruções em TNT:

"b é uma potência de 2"

e

"b é uma potência de 10"

Você seguintes respostas correctas:?

(Assumindo '?' para significar 'existe um número'):

?x: (x.x = b)

i. "Existe um número 'x' tal que x multiplicado x é igual a b"

Se isso estiver correto, então a próxima é igualmente trivial:

?x: (x.x.x.x.x.x.x.x.x.x = b)

Estou confuso porque o autor indica que eles são complicados e que a segunda deve-se levar horas para resolver; Devo ter perdido algo óbvio aqui, mas eu não posso vê-lo!

Foi útil?

Solução

Suas expressões são equivalentes às demonstrações "b é um número quadrado" e "b é o poder dia 10 de um número", respectivamente. Convertendo "poder de" declarações em TNT é consideravelmente mais complicado.

Outras dicas

Em geral, eu diria "b é uma potência de 2" é equivalente a "cada divisor de b exceto 1 é um múltiplo de 2". Ou seja:

?x ((?y (y * x = b & ¬ (x = S0))) ? ?z (SS0 * z = x))

EDIT: Isto não funciona para 10 (obrigado pelos comentários). Mas pelo menos ele funciona para todos os primos. Desculpe. Eu acho que você tem que usar algum tipo de codificação de seqüências depois de tudo. Sugiro "incompletude teoremas de Gödel" por Raymond Smullyan, se você quiser uma abordagem detalhada e mais geral para isso.

Ou você pode codificar seqüências de números usando o restante chinês Teorema, e então codificar recursivo definições, de modo que você pode definir exponenciação. Na verdade, isto é, basicamente, como você pode provar que Peano aritmética é turing completa.

Tente isto: 

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

Em seguida 

∃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))))

deve indicar "b é de alimentação de 10", na verdade dizer "não é um número igual a y e um número k tal que y é o produto de números primos distintos, e a sequência codificada por k throug estes números primos começa com 1, tem a propriedade que o elemento seguinte c de um 10 é * um, e termina com b "

Não há uma solução para o "b é uma potência de 10" problema atrás do botão saqueador no post de cientista cético aqui . Depende do teorema restante chinês da teoria dos números, bem como a existência de sequências aritméticas arbitrariamente de comprimento de números primos. Como Hofstadter indicado, não é fácil chegar a, mesmo se você sabe os teoremas apropriados.

como sobre: ??

?x: ?y: (SSx · y = b ? ?z: z · SS0 = SSx)

(em Inglês: qualquer elemento b que é = 2 deve-se ser divisível por 2; literalmente: para todos os números naturais x e y, se (2 + x) * y = b, então isso implica que há um número natural z de tal modo que z = 2 * (2 + x).)

Eu não estou 100% de certeza que isso é permitido na sintaxe do TNT proposicional cálculo , tem sido um GEB tempo desde que eu perused.

(edit:. Para a b = 2 n problema, pelo menos, posso ver por que o 10 n seria mais difícil, pois 10 não é primo Mas 11 < sup> n seria a mesma coisa, exceto substituindo o termo "SS0" com "SSSSSSSSSSS0".)

Ao expressar "b é uma potência de 10", você realmente não precisa do chinês do resto Teorema e / ou codificação das sequências finitas. Você pode, alternativamente, funcionam da seguinte forma (usamos os símbolos usuais como |,>, c-d, como atalhos para fórmulas / termos com significado óbvio):

  1. Para um número primo p, vamos denotar EXP (p, a) alguma fórmula em TNT dizendo que "p é um primo e uma é uma potência de p". Nós já sabemos, como construir um. (Por razões técnicas, não consideramos S0 a ser uma potência de p, então ~ EXP (p, S0).)

  2. Se p é primo, definimos EXP p (c, a) ? ?EXP (p, a) ? (c-1) | (a-1)?. Aqui, o símbolo | é um atalho para "divide", que podem ser facilmente definidos em TNT utilizando um quantificador existencial e multiplicação; o mesmo é válido para c-1 (a-1, resp.), que significa "o d tal que Sd = c" (Sd =, um resp.).
    Se EXP (p, c) realiza (isto é, c é uma potência de p), a fórmula EXP p (c, a) diz que "um é um poder de c" desde um = 1 (mod c-1), em seguida.

  3. Ter uma propriedade P de números (ou seja, inteiros não negativos), há uma maneira como se referir, em TNT, para o menor número com esta propriedade: ?P (a) ? ?c: ?a> c ? ~ P (a) ??.

  4. Podemos afirmar a fórmula expressando "b é uma potência de 10" (para melhor legibilidade, omitimos os símbolos ?e?, e escrevemos 2 e 5 em vez de SS0 e SSSSS0):
    ?a: ?c: ?d: (EXP (2, um) ? EXP (5, c) ? EXP (5, d) ? d> b ? a·c = b ? ?e: (E> 5 e ? | c ? EXP 5 (e, c) ? ~ EXP 5 (e, d)) ? ?e :( "e é o menor tal que EXP 5 (c, e) ? EXP 5 (d, e)" ? (d-2) |. (AE)))

Explicação: Nós escrevemos b = a·c = 2 x ·5 y (x, y> 0) e escolher d = 5 z > b de tal forma que uma z e y são primos entre si (por exemplo, Z pode ser um primo). Em seguida, "o menor e ..." é igual a (5 z ) y = d y = 2 y (mod d-2), e (d-2) | (eA) implica a = 2 x = e mod (d-2) = 2 y (nós tem 'd-2> 2 y ' e 'd-2> a', também), e assim por x = y.

Observação: Esta abordagem pode ser facilmente adaptada para definir "b é uma potência de n" para qualquer número N com uma decomposição fixo um 1 2 ... k , onde cada um i é uma potência de um primo p i e p i = p j ? i = j.

Aqui está o que eu vim com:

?c: ?d: <(* c d = b) ? <(c = SO) v?e: (d = e * SSO) >>

que se traduz em:

Para todos os números de c, existe um número d, de tal modo que se c tempos de d iguais b então ou c é 1 ou existe um número e tal que d é igual a 2 vezes e.

ou

Para todos os números de c, existe um número d, de tal modo que, se b é um factor de C e D, em seguida, quer c é 1 ou d é um factor de 2

ou

Se o produto de dois números é, em seguida, b um deles é 1 ou um deles é divisível por 2

ou

Todos os divisores de b são 1 ou são divisível por 2

ou

b é uma potência de 2

Eu acho que a maioria dos acima só têm mostrado que b deve ser um múltiplo de 4. Como sobre este: ?b: ?c: << ?e: (c · e) = b & ~ ?c ': ?c '' :( SSC '· SSC' ') = c> ? c = 2>

Eu não acho que a formatação é perfeito, mas ele lê:

Existe b, de tal forma que para todos c, se c é um fator de b e c é primo, então c igual a 2.

Aqui está o que eu vim com para a instrução "b é uma potência de 2"

?b: ?a: ~ ?c: ((a SS0 *) + sss0) * C = b

Eu acho que isso diz "Existe um número b, de tal forma que para todos os números um, lá não existe um número c tal que (a * 2) + 3 (em outras palavras, um maior número ímpar de 2) multiplicado por c, dá-lhe b ". Então, se b existe, e não pode ser zero, e não tem divisores ímpares superior a 2, então não seria b necessariamente ser 1, 2, ou de outra potência de 2?

Para a expressão aberta o que significa que b é uma potência de 2, eu tenho ∀a:~∃c:(S(Sa ∙ SS0) ∙ Sc) = b

Isso efetivamente diz que para toda a, S (Sa · SS0) não é um fator de b. Mas, em termos normais, S (Sa · SS0) é 1 + ((a + 1) * 2) ou 3 + 2a. Agora podemos reformular a declaração como "nenhum número ímpar que é pelo menos 3 é um fator de b". Isto é verdade se e somente se b é uma potência de 2.

Eu ainda estou trabalhando no b é uma potência de 10 problema.

minha solução para b é uma potência de dois é: ?x: ?y X.Y = b (isPrime (x) => x = SS0)

isPrime () não deve ser difícil de escrever.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top