FTC 2023 02 SistemasFormais 03 Exemplo

FUNDAMENTOS TEÓRICOS DA
COMPUTAÇÃO
-- SISTEMAS FORMAIS --
Exemplos de Sistemas Formais
Sistema MIU
Um sistema formal básico
Um sistema formal é uma linguagem sobre algum alfabeto de símbolos junto
com axiomas e regras de inferência que separam/geram algumas das strings
na linguagem como teoremas
O alfabeto de símbolos são “básicos” porque não necessariamente têm
significado inerente (sintaxe). Estes são considerados “bem formados” se sua
estrutura seguir as regras estabelecidas por esses sistemas
Será definido um sistema formal básico, conhecido como “sistema MIU”
A estrutura lógica do sistema "MIU" foi criada por Emil Post, considerado um
dos fundadores da teoria da computabilidade
Post trabalhou no início de 1900 e, como muitos matemáticos da época,
estava preocupado com os fundamentos da matemática e o que seria possível
provar
Sistema MIU
Axioma
Em qualquer sistema formal, primeiro devemos saber quais os objetos que
possuímos
Os objetos são a base e podem ser pensados como axiomas do nosso
sistema
No sistema MIU, o único objeto (axioma) com o qual começamos é MI

Em seguida, podemos usar regras para expandir os objetos que temos
Sistema MIU
Regras
Regra 1: Se você tem um objeto x que termina em I, então você pode gerar
um objeto que é xU (note que o ! ∈ #)
Então, o que podemos fazer com essa regra? Podemos usá-lo para
adicionar outro objeto à nossa coleção
Atualmente possuímos apenas o objeto MI, mas podemos usar a Regra 1

para gerar um outro objeto MIU
Observe que não podemos aplicar a Regra 1 a MIU, pois ela termina em U
É importante esclarecer que x pode representar qualquer objeto genérico
Agora temos dois objetos
Sistema MIU
Regras
Vamos definir as outras três regras do sistema MIU
Regra 2: Se você tem um objeto da forma Mx, então você pode gerar um
outro objeto da forma Mxx
Regra 3: Se você tiver um objeto com a estrutura III em qualquer lugar,

então você pode gerar um objeto que substitua III por U
Regra 4: Se a estrutura UU ocorrer em qualquer lugar do seu objeto, você
poderá gerar um novo objeto sem ela
Sistema MIU
Usando as regras para gerar novos objetos
A regra 2 nos permite expandir o tamanho de um objeto muito rapidamente
Podemos obter MII, MIIII, MIIIIIIIII e assim por diante apenas aplicando a
Regra 2 a MI repetidamente
As regras 1 e 2 nos permitem fazer objetos de comprimento maior, e as

regras 3 e 4 nos permitem fazer objetos de comprimento menor
Aplicando Regra 3, poderíamos pegar MIIIIIIII e fazer MIUIIII, MIIUIII, ou
mesmo MIIUU
A aplicação da Regra 4 ao MIIUU nos devolve o MII

Sistema MIU
O desafio que Hofstadter propôs, após definir este sistema, é: será que é
possível gerar o objeto MU?
Sistema MIU
Usando as regras para gerar novos objetos

Eu encorajo você a mexer com essas regras e construir uma “coleção” de
objetos
Passe algum tempo nisso antes de seguir em frente!
Se você não quiser escrevê-lo, recomendo usar este site
http://miu.edlogic.co.uk.s3-website-eu-west-1.amazonaws.com/
que permite jogar com o sistema MIU online
Ou este outro que te guia dando as opções disponíveis a cada passo -
https://demonstrations.wolfram.com/MIUExplorer/
Sistema MIU
Sistema MIU
Sistema MIU
Sistema MIU
Sistema MIU
https://demonstrations.wolfram.com/MIUExplorer/
Sistema MIU
Resposta do enigma
É impossível fazer MU a partir de MI
Na página da Wikipedia (https://en.wikipedia.org/wiki/MU_puzzle) tem
uma prova do motivo exato pelo qual você não pode fazer MU
Esta prova baseia-se em fazer observações sobre a estrutura das próprias
regras, em vez dos objetos (tem a ver com a quantidade de I que teria que
ser divisível por 3)
O fato de não podermos fazer MU depende inteiramente do objeto inicial
Se tivéssemos começado com MUUU, poderíamos criar MU
Se tivéssemos começado com MIII, também geraríamos MU
Sistema MIU
Sintaxe e semântica
O sistemas MIU 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, dentro do sistema, um algoritmo poderia gerar sucessivas
cadeias de símbolos válidas em uma tentativa de gerar MU
Para um humano, eventualmente, percebe-se que o sistema é de alguma
forma sobre a divisibilidade por três dos Is. Este é o nível "semântico" do
sistema - um nível de significado que o sistema atinge naturalmente
Há um “salto para fora do sistema” e começa-se a raciocinar sobre o
sistema, em vez de trabalhar dentro do sistema
Neste nível semântico, o quebra-cabeça MU pode ser visto como impossível
Sistema MIU
Interesse por sistemas formais
Por que tantos matemáticos estavam interessados em sistemas formais? É
porque essas eram versões simples da própria matemática!
MI é um axioma do sistema. Também podemos pensar nas Regras 1-4 como
métodos de prova, como indução, contradição e raciocínio formal
Usando as Regras 1–4 podemos gerar novos objetos, que são os teoremas
Os matemáticos usaram sistemas formais para fazer algumas previsões
surpreendentes sobre nossas limitações com a matemática, como o Teorema
Incompletude de Gödel
Este teorema basicamente afirma que qualquer sistema formal consistente
não será capaz de provar tudo sobre os números naturais. Essa é uma
grande afirmação!
Sistema pq-
Definição
Este sistema formal também foi inventado por Hofstadter
Alfabeto: {p, q, –}
Sintaxe: As strings da linguagem têm a forma de um ou mais hífens seguidos
de p seguido de um ou mais hífens seguidos de q seguido de um ou mais
hífens
Sejam x e y sequências de um ou mais hífens
Axioma: xp-qx-
Regra de Inferência: xpyqz → xpy-qz-
Sistema pq-
Alguns teoremas
(1) --p-q--- Axioma
(2) --p--q---- De (1) aplicando a regra
(3) -p-q-- Axioma
(4) -----p-q------ Axioma
(5) -----p--q------- De (4) aplicando a regra
(6) -----p---q-------- De (5) aplicando a regra
(7) -----p----q--------- De (6) aplicando a regra
Sistema pq-
Exercícios
(1) ---p----q------- é um teorema? Por quê?
(2) ---p-----q------- é um teorema? Por quê?
(3) ---p--p--q------- é um teorema? Por quê?
(4) O que você acha que esses teoremas significam?
Sistema pq-
Isomorfismo no sistema pq
p ⇔ mais
q ⇔ igual
sequência de n traços ⇔ n
Exemplo: --p-q---
Exemplo: -----p----q---------
Sistema pq- modificado
Definição
Este sistema formal também foi proposto por Hofstadter
Alfabeto: {p, q, –}
Sintaxe: As strings da linguagem têm a forma de um ou mais hífens seguidos
de p seguido de um ou mais hífens seguidos de q seguido de um ou mais
hífens.
Sejam x e y sequências de um ou mais hífens
Axioma 1: xp-qx-
Axioma 2: xp-qx
Regra de Inferência: xpyqz → xpy-qz-
Sistema pq- modificado
Inconsistência?
(1) --p-q--- Axioma 1
(2) --p-q-- Axioma 2
(3) --p--q--- De (2) pela regra
Quer dizer, 2+1=3, 2+1=2 e 2+2=3? Nosso sistema é inconsistente?
É apenas inconsistente em relação à antiga interpretação onde q significava
"igual”, mas se alterarmos para "maior ou igual a" nos permite "recuperar"
a consistência
Referências
Douglas Hofstadter. Godel, Escher, Bach: An Eternal Golden Braid. Editora

Basic Books. 1999.
https://www.cantorsparadise.com/your-first-formal-system-da2fffbf7888
https://cs.lmu.edu/~ray/notes/formalsystems/

FTC 2023 02 SistemasFormais 03 Exemplo

Enviado por

Direitos autorais:

Formatos disponíveis

FTC 2023 02 SistemasFormais 03 Exemplo

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

FTC 2023 02 SistemasFormais 03 Exemplo

Enviado por

Direitos autorais:

Formatos disponíveis

FUNDAMENTOS TEÓRICOS DA

No sistema MIU, o único objeto (axioma) com o qual começamos é MI

Atualmente possuímos apenas o objeto MI, mas podemos usar a Regra 1

Regra 3: Se você tiver um objeto com a estrutura III em qualquer lugar,

As regras 1 e 2 nos permitem fazer objetos de comprimento maior, e as

A aplicação da Regra 4 ao MIIUU nos devolve o MII

Usando as regras para gerar novos objetos

Douglas Hofstadter. Godel, Escher, Bach: An Eternal Golden Braid. Editora

Você também pode gostar