Aula 12 - O Problema da Parada - Parte 3

Oi ó tá beleza então a gente aprendeu como representar uma máquina de turing utilizando 01 uma máquina de tudo que recebe como entrada uma cadeia de 01 então tanto a cadeia de entrada quanto ela própria são representadas através de 01 Ok E aí quando a gente fala de representação de uma máquina de turing iene a gente usa esse tema aqui ó rdm tá a representação de m3001 o Ok vamos então para o nosso teorema que a gente quer provar aqui e o problema da parada para máquina de turing é indecidível é isso que a gente

quer provar tá que ele é indecidível Ou seja que tem um problema indecidível é aquele que você não consegue provar que ele Sara e nem sim e nem que não tem Olá a prova que a gente vai fazer aqui é por contradição tá então a gente para fazer uma prova contradição a gente assumi o contrário você é verdade e aí se essa ao assumir esse isso chegar não contradição é que essa essa isso que foi assumida mentira Esse é isso é mentira então o contrário é verdade ok a gente vai assumir que ela é decidível

tá e para summit ela decidiu então eu vou ter uma máquina de trh e resolve esse problema tá se ela decidiu essa e essa máquina de lavar resolver o problema agradecido E aí eu tenho a máquina de furar a que resolve esse problema e ela recebe uma cadeia como entrada e essa cabeça é só é aceita se aí eu tenho duas condições para isso primeira é que essa cadeia que eu vou receber Ela é composta por duas partes a primeira parte é a representação da minha máquina de turing meme a segunda parte é uma cadeia

w o Ou seja eu vou receber uma única entrada Só que essa única entrada ela tem duas partes a primeira parte é a representação em binário de uma máquina de turing m e a segunda parte é a cadeia w também Dinara tá E aí beleza se a primeira condição é uma cadeia só vai ser aceita por hagacy satisfazer essa primeira condição esse a computação de m com a entrada w parar é a Então essa minha Cadê aqui que é O que é composta pela representação da máquina de turing iene e pela cadáver a gente vai

rodar essa essa essa máquina de turing meme com essa cadeira w aqui É sim e me para a executar WH também para mais isso que nada melhor que um grafo gráfico para ilustrar isso pra gente e é importante dizer que também que se nem se nem é essa condição aqui e nem essa condição aqui for satisfeita E aí a minha minha máquina de turing em H ela vai rejeitar essa cadeia tá Ah tá beleza que ilustrativamente como é que isso eu fico como é que isso fica eu tenho a minha máquina a minha representação de

m aqui e w ou seja se que a minha cadeia de entrada para minha máquina H E aí se M ao Executar a entrada w para tão a minha a máquina H aceita E agora se eu rodar m com w&m não parar aí a minha máquina da H rejeita quem tá um causa aí análise esse aqui entende que é um pouco tem uma manhãzinha despedida dar uma digerido para entender esse direitinho entendeu vamos para a próxima etapa aqui o agente supõe que exista essa máquina Agora tá esse ela funciona dessa forma ela decide vó tá

ela aceita se para aqui ela é gente assim não para aqui tá cara decidiu vamos ver se isso vai levar a gente alguma contradição para isso a gente vai construir uma máquina de turing a galinha tá na galinha a galinha a galinha a galinha Oi e aí essa minha máquina de turing A Galinha ela vai ser igual a máquina aí de trem H só que eu vou inverter esses resultados aqui ó e ela vai a rodar indefinidamente sempre th termina em um estado de aceitação ó e vai aceitar caso ela termina estado de rejeição tá

então ela é a minha máquina a galinha vai ser a os resultados invertidos ele tá a mesma da aqui só aqui sempre que aceitar aqui eu vou colocar uma nova transmissão lá vou fazer uma modificação sempre que aceitar foi o estado de aceitar aqui na verdade ela vai rodar indefinidamente e sempre ficou rejeita que ela vai aceitar Beleza então essa é a única alteração da minha máquina de turing em a galinha E aí beleza agora eu vou combinar essa máquina de misturar a galinha e com uma máquina de cópia Oi e aí combinando tudo isso

eu vou ter uma máquina de turing de É parece meio confuso mas com calma que com paciência a gente consegue entender Estou brincando com essa ideia de máquinas de trem tá eu tenho H construir a galinha e agora eu vou combinar outras máquinas de torno para construir a máquina de turing de a partir dessas que a gente já criou a minha a máquina de turing de um e ela recebe é uma representação de uma máquina de turing tá a entrada para ver essa nova máquina de tudo que eu vou criar é uma máquina de turing

a representação de uma máquina de tô nem aí e essa minha máquina de turing deixa eu vou criar e ela vai copiar essa entrada aqui é construído construindo a duplicação de ou seja vai construir isso aqui tá esse é o que a máquina de cópia faz E aí a ela em série é centrada que ela gerou aqui na máquina a galinha Oi tá ilustrando como é que fica isso aqui eu tenho a minha entrada e se a representação do a máquina e me isso aqui eu coloco como entrada em uma máquina de turing capaz de

copiar rgm então RM se torna rmr GM era do peito e isso aqui vai ser vídeo entrada para minha máquina a galinha Oi e aí essa se vocês lembrarem da definição de A Galinha ela investe o resultado DH o que significa isso e me para si n para com a entrada rdm e ela roda indefinidamente E agora se ele não para com a entrada RM E aí ela para é porque rdm é entrada para máquina e me é isso rdm seria como se fosse meu w esse w aqui vai ser rodado em m Ah tá

fim da pausa aqui de novo e tenta digerir essa ilustração aqui tá assim que você sair digerir a gente continua aqui aí a gente pode observar aqui essa máquina de turing vender ela vai receber a representação de qualquer máquina de tudo Tá se a qualquer máquina de trem então pode receber Ela própria tá e o que Qualquer máquina de turing gente pode representar com 1001 e então ela pode receber como entrada a representação dela própria tá E aí reescrevendo diagrama com essa nova informação a gente tem esse tchau é a minha máquina de turing ter

recebe a representação de uma entrada 1 e copia e essa entrada VIP para ir a RD RD Oi e aí eu aplicar centrada aqui em a galinha a galinha faz o quê ó ó se de e ao Executar a entrada RG de para e de lá então vai rodar indefinidamente tá esse aqui é o resultado de dele E agora se de Não Para e com a entrada RD E aí ela para e olha a contradição aqui ó ó e se de não para com a entrada RD ela para 1cd e para com a entrada RD

ela roda indefinidamente a gente tem uma baita contradição aqui certo o CID para ela não para esse depara-se de não para ela para tá pausa novamente de Gere isso aqui é um pouquinho eu tô com a palavra em inglês de truque é um pouquinho tem uma artimanha que você digerir tudo isso aqui Ah mas isso é a nossa conclusão de que a gente acabou de provar tá porque a gente construiu este diagrama aqui a partir da suposição de que existe h tá Ou seja que o problema da parada decidível e ao manipular essa suposição logo

logo a gente chegou numa contradição se a gente chegou na contradição é porque essa nossa suposição Inicial ela é falsa e se essa suposição e também é uma prova na parada desse digo ela é falsa e ela produz essa contradição então portanto podemos concluir que o problema da parada é indecidível e eu aconselho você sair e voltar nesse nesse vídeo tá nesse conjunto de vídeo dessa aula aqui para entender essa prova porque ela é uns problema alguns temas mais fundamentais a gente tem na teoria da computação e isso aqui é base para que a gente

possa provar ainda e sibilidade de outros problemas através da redução isso é que a gente vai ver na nossa próxima aula