Quebra-cabeça MU - MU puzzle

O quebra - cabeça MU é um quebra-cabeça declarado por Douglas Hofstadter e encontrado em Gödel, Escher, Bach envolvendo um sistema formal simples chamado "MIU". A motivação de Hofstadter é contrastar o raciocínio dentro de um sistema formal (ou seja, derivando teoremas) com o raciocínio sobre o próprio sistema formal. MIU é um exemplo de sistema pós-canônico e pode ser reformulado como um sistema de reescrita de strings .

O quebra-cabeça

Suponha que existam os símbolos M, Ie Uque podem ser combinados para produzir cadeias de símbolos. O quebra-cabeça MU pede que se comece com a string "axiomática" MIe a transforme na string MUusando em cada etapa uma das seguintes regras de transformação:

Nr.	Regra formal			Explicação informal	Exemplo
1	xI	→	xIU	Adicione um Uao final de qualquer string terminando emI	MI	para	MIU
2	Mx	→	Mxx	Dobre a corda após o M	MIU	para	MIUIU
3	x IIIy	→	x Uy	Substitua qualquer IIIum por umU	MUIIIU	para	MUUU
4	x UUy	→	xy	Remova qualquer UU	MUUU	para	MU

Solução

O quebra-cabeça não pode ser resolvido: é impossível transformar a string MIem MUaplicando repetidamente as regras fornecidas. Em outras palavras, MU não é um teorema do sistema formal MIU. Para provar isso, é preciso "sair" do próprio sistema formal.

Para provar afirmações como essa, geralmente é benéfico procurar um invariante ; ou seja, alguma quantidade ou propriedade que não muda durante a aplicação das regras.

Nesse caso, pode-se observar o número total de Iem uma string. Apenas a segunda e a terceira regras mudam esse número. Em particular, a regra dois o dobrará, enquanto a regra três o reduzirá em 3. Agora, a propriedade invariável é que o número de Inão é divisível por 3:

• No início, o número de Is é 1, que não é divisível por 3.
• Dobrar um número que não é divisível por 3 não o torna divisível por 3.
• Subtrair 3 de um número que não é divisível por 3 também não o torna divisível por 3.

Assim, o objetivo de MUcom zero Inão pode ser alcançado porque 0 é divisível por 3.

Na linguagem da aritmética modular , o número n de Iobedece à congruência

${\ displaystyle n \ equiv 2 ^ {a} \ not \ equiv 0 {\ pmod {3}}. \,}$

onde a conta com que frequência a segunda regra é aplicada.

Um critério decidível para derivabilidade

De modo mais geral, um dado arbitrariamente seqüência x pode ser derivada a partir MIdo acima quatro regras , se, e somente se , x aspectos, os três seguintes propriedades:

1. x é composto apenas por um Me qualquer número de Ie U,
2. x começa com M, e
3. o número de Iem x não é divisível por 3.

Prova

Só se: Nenhuma regra move o M, altera o número de M, ou introduz qualquer personagem de M, I, U. Portanto, todo x derivado de MIrespeita as propriedades 1 e 2. Como mostrado antes , ele também respeita a propriedade 3.

Se: Se x respeita as propriedades de 1 a 3, seja e o número de e em x , respectivamente, e seja . Pela propriedade 3, o número não pode ser divisível por 3, portanto, também não pode ser. Ou seja ,. Deixe tal que e . Começando com o axioma , aplicando a segunda regra, o tempo obtém ... com . Como é divisível por 3, pela construção de , aplicando a terceira regra vezes obterá ... ... , com exatamente com , seguido de algum número de . A contagem pode ser sempre uniforme, aplicando a primeira regra uma vez, se necessário. Aplicando a quarta regra com frequência suficiente, todos podem ser excluídos, obtendo-se assim ... com . Aplicar a terceira regra para reduzir trigêmeos em a nos locais certos obterá x . Ao todo, x foi derivado de . ${\ displaystyle N_ {I}}$${\ displaystyle N_ {U}}$IU${\ displaystyle N = N_ {I} + 3N_ {U}}$${\ displaystyle N_ {I}}$${\ displaystyle N}$${\ displaystyle N \ equiv 1 {\ text {ou}} N \ equiv 2 {\ pmod {3}}}$${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle 2 ^ {n}> N}$${\ displaystyle 2 ^ {n} \ equiv N {\ pmod {3}}}$MI${\ displaystyle n}$MIIII${\ displaystyle 2 ^ {n}}$ I${\ displaystyle 2 ^ {n} -N}$${\ displaystyle n}$${\ displaystyle {\ frac {2 ^ {n} -N} {3}}}$MIIIIUU${\ displaystyle N}$ IUUUMIIII${\ displaystyle N_ {I} + 3N_ {U}}$ IIUMI

Exemplo

Para ilustrar a construção no Se parte da prova, a corda MIIUII, que respeite as propriedades de 1 a 3, conduz a , , , ; pode ser derivado da seguinte forma: ${\ displaystyle N_ {I} = 4}$${\ displaystyle N_ {U} = 1}$${\ displaystyle N = 7}$${\ displaystyle n = 4}$

MI ${\ displaystyle {\ stackrel {2} {\ to}}}$ MII ${\ displaystyle {\ stackrel {2} {\ to}}}$ MIIII ${\ displaystyle {\ stackrel {2} {\ to}}}$ MIIIIIIII ${\ displaystyle {\ stackrel {2} {\ to}}}$ MIIIIIIIIIIIIIIII ${\ displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUIIIIII ${\ displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUUIII ${\ displaystyle {\ stackrel {1} ​​{\ to}}}$ MIIIIIIIUUIIIU ${\ displaystyle {\ stackrel {3} {\ to}}}$ MIIIIIIIUUUU ${\ displaystyle {\ stackrel {4} {\ to}}}$ MIIIIIIIUU ${\ displaystyle {\ stackrel {4} {\ to}}}$ MIIIIIII ${\ displaystyle {\ stackrel {3} {\ to}}}$ MIIUII.

Aritmetização

O capítulo XIX de Gödel, Escher, Bach fornece um mapeamento do sistema MIU para a aritmética, como segue. Em primeiro lugar, cada MIU-corda pode ser traduzido para um número inteiro, mapeando as cartas M, Ie Upara os números 3, 1 e 0, respectivamente. (Por exemplo, a string MIUIUseria mapeada para 31010.)

Em segundo lugar, o único axioma do sistema MIU, ou seja, a string MI, torna-se o número 31.

Terceiro, as quatro regras formais fornecidas acima tornam-se as seguintes:

Nr.	Regra formal			Exemplo
1	k × 10 + 1	→	10 × ( k × 10 + 1)	31	→	310	( k = 3)
2	3 × 10 m + n	→	10 m × (3 × 10 m + n ) + n	310	→	31010	( m = 2, n = 10)
3	k × 10 m + 3 + 111 × 10 m + n	→	k × 10 m + 1 + n	3111011	→	30011	( k = 3, m = 3, n = 11)
4	k × 10 m + 2 + n	→	k × 10 m + n	30011	→	311	( k = 3, m = 2, n = 11)

( NB: A tradução da primeira regra acima difere superficialmente daquela no livro, onde está escrito como "[i] f fizemos 10 m  + 1, então podemos fazer 10 × (10 m  + 1)". Aqui, no entanto, a variável m foi reservada para uso em expoentes de 10 apenas e, portanto, foi substituída por k na primeira regra. Além disso, nesta renderização, a disposição dos fatores nesta regra foi feita consistente com a da outra três regras.)

Relação com a lógica

O sistema MIU ilustra vários conceitos importantes em lógica por meio de analogia.

Pode ser interpretado como uma analogia para um sistema formal - um encapsulamento de conceitos matemáticos e lógicos usando símbolos. A string MI é semelhante a um único axioma e as quatro regras de transformação são semelhantes às regras de inferência .

A string MU e a impossibilidade de sua derivação são então análogas a uma declaração de lógica matemática que não pode ser provada ou refutada pelo sistema formal.

Também demonstra o contraste entre a interpretação no nível "sintático" dos símbolos e no nível "semântico" dos significados. No nível sintático, não há conhecimento da insolubilidade do quebra-cabeça MU. O sistema não se refere a nada: é simplesmente um jogo envolvendo cordas sem sentido. Trabalhando dentro do sistema, um algoritmo poderia gerar sucessivamente todas as cadeias de símbolos válidas em uma tentativa de gerar MU e, embora nunca tivesse sucesso, pesquisaria para sempre, nunca deduzindo que a busca era inútil. Para um jogador humano, entretanto, depois de várias tentativas, logo começa-se a suspeitar que o quebra-cabeça pode ser impossível. A pessoa então "pula para fora do sistema" e começa a raciocinar sobre o sistema, em vez de trabalhar dentro dele. Eventualmente, percebe-se que o sistema é de alguma forma sobre a divisibilidade por três. Este é o nível "semântico" do sistema - um nível de significado que o sistema atinge naturalmente. Neste nível, o quebra-cabeça MU pode ser visto como impossível.

A incapacidade do sistema MIU de expressar ou deduzir fatos sobre si mesmo, como a incapacidade de derivar MU, é uma consequência de sua simplicidade. No entanto, sistemas formais mais complexos, como sistemas de lógica matemática, podem possuir essa habilidade. Essa é a ideia-chave por trás do Teorema da Incompletude de Gõdel .

Usos pedagógicos

Em seu livro, Matemática Discreta com aplicações , Susanna S. Epp usa o enigma MU para introduzir o conceito de definições recursivas , e começa o capítulo relevante com uma citação de GEB .

Veja também

• Invariante (matemática)
• Gramática irrestrita

Notas

Referências

links externos

• "Sistema MIU de Hofstadter" . Arquivado do original em 4 de março de 2016 . Retirado em 29 de novembro de 2016 . Uma interface online para produzir derivações no Sistema MIU.
• "MU Puzzle" . Arquivado do original em 14 de maio de 2018 . Página visitada em 13 de maio de 2018 . Uma implementação JavaScript online do sistema de produção MIU.