Aula 12 - O Problema da Parada - Parte 2

E qual é esse problema não decidir que a gente vai provar aqui é um dos problemas mais fundamentais da teoria da Computação como eu já falei a sua prova é relativamente simples era um pouco você precisa digerir um pouco essa prova que a gente eu vou apresentar para vocês mas é relativamente simples e uma vez que você entendeu e ela que você conseguiu provar esse esse problema o sendo não decidível você pode utilizar ele e como problemar para provar que um outro problema b não é decidível também tá bom então mas isso é questão da

próxima aula primeira gente vai te provar ele aqui ó como é que eu defini esse problema da parada da dá uma máquina de turing arbitrária então tem uma máquina de turing qualquer lá que eu chamo de n e essa máquina de turing ela trabalha com alfabeto de entrada cima é um Você tem uma string w é uma cadeia w pertencente a esse alfabeto tá a qualquer interação desses alfabeto E aí a pergunta que se faz é acutação DM com a entrada W vai parar se eu perguntar isso Essa é a primeiro que significa isso eu

vou aí eu vou colocar w como entrada na máquina de turing m Oi e aí eu pergunto e ao rodar ao computar m qual é as entrada w essa computação vai parar ah ah eu provei se esse e esse trem provar que esse problema aqui não é decidível Ou seja aqui que eu não tenho como provar ele a ser decidível então eu vou utilizar uma estratégia de e a o contraditório não como chama já absurdo provar for absurdo tá como que eu faço então então eu eu falo inicialmente eu assumo que esse problema é decidível

Ou seja que ele para e me traz uma resposta tá tô Assumo isso uma vez que eu assumi isso se essa suposição me levar a uma contradição tá aí se achando no respirar lembrar contradição próprio suas para vapor contradição se essas essa suposição me leva a uma contradição Então significa que essas posição inicial ela é falha logo o problema não é decidido tá essa estratégia e como que a gente vai fazer isso Oi ó Antes de mostrar a prova eu preciso primeiro preparar o terreno aqui tá E aí nessa preparação do terreno a gente vai

entender como que eu eu represento tanta minha cadeia de entradas e com apenas com um símbolo 01 E quanto a minha própria máquina de turing eu posso representar ela apenas com 01 toda aquela que ela estrutura de estados transições e tal eu consigo transformar tudo isso em 01 tá consigo representar isso através de zeros e uns e como é que eu faço isso e vamos supor vamos supor que eu tenho essa máquina de turing aqui que tem os Estados quiseram Até quem quiser 12 até quem tá e supondo que o que zero seja o meu

estado Inicial Eu vou representar essa minha máquina de tudo utilizando apenas o conjunto binário 01 e a minha fita vai ter apenas o símbolo zeros uns e Branco em João entender agora o que a gente vai fazer uma máquina de turing Ela é completamente definida pela sua função de transição uma vez que o definir todas as minhas transições o seu definir todas as transições de uma máquina de turing é automaticamente eu também definir todos os meus estados é isso eu não vou ter um estado que não está dentro de uma transição eu baixo eu defini

as transmissões o seu d-fine todas as transições eu também vou pegar todos os símbolos de entradas possíveis certo se eu não tenho esses embrulha representado na minha nas ministrações então ele também não faz parte do meu alfabeto então basta definir as transições que eu defino toda a minha máquina de tudo que como que eu defini uma transição que que é uma transição em primeiro lugar a contradição de Jeová cantor determinística ela tem a seguinte forma Então ela se a função de transição ela é representada dessa forma aqui eu tô no estado que ir qualquer a

receber a entrada X e essa minha transmissão Então vai me levar para o estado que J é o símbolo x eu vou trocar pelo símbolo Y na minha fita e eu vou ter um de aqui que representa a minha direção eu vou para a esquerda ou se eu vou para a direita sempre me a tradição sempre vai ser isso um estado de origem um estado destina o que que eu tô lendo da minha fita e o que que eu vou colocar no lugar disso na minha fita e depois para onde que eu vou se eu

vou para a esquerda se eu vou para direito tá E aí como que eu pude fico tudo isso é o símbolo zero ele vai ter a classificação 1 e o meu símbolo um ele vai ter a codifi cação 1 o meu símbolo branco vai ter a codifi cação 11 é só que eu já representei todo o meu alfabeto de fita em Hinário e em lá não utilizando apenas os símbolos um tá aí agora eu posso representar a os meus estados o que zero eu chamo de um o que uma chame de o quê Dois de

um e assim por diante até o meu último estado que M que eu botei um número de 1 é igual ao número de gene com mais um número um tá então essa expressão aqui um elevado a n + 1 às vezes tá a beleza e aí eu tenho amanhã a é a minha direção para a esquerda representada pelo símbolo um e a minha direção para a direita representado pelo meu símbolo um um OK aí agora vamos supor aqui essa representação aqui ó cê aparentes fez parentes dizer significa codifi cação do símbolo Z Ah tá então

10 você quiser é meu Z os pezinho a classificação de 0 então é um tá vamos supor que sei dizer aqui sendo meu z u r c Dr é o CDR é um e quem tá beleza essa é a minha classificação é isso é como representa a minha classificação aí eu tenho que eu tenho uma transição da forma que a gente já viu e essa transição ela vai ser codificada da seguinte forma e eu vou ter aqui a codifi cação do meu estado de origem e depois 10 depois a codifi cação do meu estado destino

não notificação do meu símbolo de entrada sendo lido depois 10 depois a codifi cação do meu estado destino Depois 10 depois a codifi cação do meu estado do símbolo que eu vou substituir x depois de 10 depois a codifi cação e da direção se eu vou para a esquerda para direita certo então eu consigo representar todo uma transição simplesmente simplesmente com 01 se admitindo esse formato pré-estabelecido aqui os uns serão as codificações zeros é o que separa tudo isso aí que que falta mais para eu definir uma máquina de tudo por completo e basta utilizar

dois zeros e consecutivos para separar as transições então eu coloco essa transição aqui depois coloco dois zeros E aí eu sei que eu vou iniciar uma próxima transição Coloca essa próxima tradição coloca 2 horas coloca a próxima atração coloca 2 horas até que eu represente todas as transições é da minha máquina de tudo tá apenas em 01 o que é que falta mais para completar isso o início e o fim da representação são então realizado por três zeros tá Eu imagino que eu tenho aqui a minha máquina de turing iniciando com três zeros E aí

depois eu tenho a codifi cação e eu tenho a codifi cação do meu estado quer ir vamos supor que seja o meu estado Inicial que é o código dele é um é isso mas tá vendo tchau código dele aí eu separo por 10 agora eu quero o código do meu x vamos supor que meu símbolo de entrada é um tá tá meu símbolo entrada é um é de qual que é o código dele é um tá vamos trocar ele aqui o saco indicação de x é vamos supor que meu estado destino seja o estado o

4G 4 e o meu que quatro aqui é essa expressão aqui quatro mais um Tá certo então vou ter 51 Então faça isso aqui ó deixa esse cara aqui troquei ele por um dois três quatro cinco e agora qual que é o meu símbolo que eu vou substituir por x vamos supor aqui é o símbolo Zé tava meu 50 é notificação dele é tão e eu vou trocar esse cara aqui por an e depois eu tenho outro zero e depois o meu estado é meu estado não a direção vamos supor que eu quero ir para

a esquerda Qual é a classificação da esquerda é o número um Beleza beleza definir aqui o início da minha e o início da minha tu não pediu essas um tipo aí essa aqui é a minha transmissão esses 30 saque significa que eu estou iniciando a representação de uma máquina de turing Se eu colocar dois zeros aqui significa que eu estou separando é mais uma transição tá então o seu corpo eu tenho a minha segunda transição aqui a gente vai traduzir para o zeros e uns Mas você já sabe como é que funciona o processo E

aí eu vou ter outra transição nosso pouco essa essa minha máquina de turing só tem três transições E aí aqui eu consigo representar em toda a minha máquina de turing utilizando os zeros e uns ok eu vou ver se a gente entender isso aqui é esse aqui é base para a gente entender como que vai funcionar o nosso e a prova Oi para o nosso problema da parada