e fala pessoal Mais uma aula aqui de teoria da Computação a gente vai continuar Mas se a gente vai virar a página tá gente vai aproveitar um pouco dos conhecimentos que a gente já viu mas agora a gente não vai trabalhar tanto com o Máquina de turing essa Essa parte a técnica algorítmica é o DJ projeto de máquina de toda a gente já a gente já viu o suficiente agora eu quero mostrar para vocês e há o problema da parada e isso é um dos problemas mais fundamentais que a gente tem na teoria da Computação
porque ele da base para gente conseguir provar o que vários problemas alguns deles são o indecidíveis tá 10 primeiro para a gente ir ver antes de ver esse problema vamos revisar aqui o quê que é um problema de se divertir é um problema indecidível a gente já viu essa figura aqui na salas passadas mas só para recapitular em todo nosso trabalho em cima de linguagens formais ela ela segue essa essa hierarquia e a gente tem aqui um conjunto pequeno de linguagem quero que a gente chama de linguagem regular que a gente trabalha com a máquina
teórica que o autômato finito depois a gente viu as linguagens Oi livre de contexto se que trabalham com o autômato de pilha e aí a gente chegou com a máquina de turing bom e se você tem um problema que tá aqui dentro desse conjunto aqui ó ainda essa bolinha aqui ele é um problema decidível esse é um problema decidi que define um problema ser decidível um problema é decidi viu e quando a máquina de turing ela sempre para para onde determinado entrada tá então se você tem um problema de decisão por exemplo você quer saber
se a E se o senhor o senhor seu a cadeia pertence a uma determinada linguagem e ela é essa máquina de furar ela sempre vai parar se ela for decidir ela vai parar para dizer que sim pertence ou ela vai parar para dizer que não não pertence Tá mas a gente pode usar isso para problemas de decisão também não não Sinceramente para a citação de linguagem mas a me fale aqui um pouco a memória mas pode ser algo bem trivial você dá as a área dessa o volume dessa garrafa aqui e perguntar se ela tá
dentro de uma determinada especificação por exemplo Esse é um problema de decisão E aí essa máquina se ela fez próprio vocês foram problema decidível essa máquina sempre vai parar e dizer que sim atende essa especificação o que não vai parar e dizer que não não atende às e a outra outro problema decidível é por exemplo se perguntar se um determinado número é um quadrado perfeito então a número quatro é um quadrado perfeito que você tem dois elevado ao quadrado numero 9 é um quadrado perfeito você tem é 3 elevada ao quadrado 16 né e assim
por diante e você coloca o número para essa maquiagem dure e ela sempre para e te disse ó é um quadrado perfeito ou não é um quadrado perfeito aqui tá beleza o que que é um problema não decidível é todo o resto tá então como a gente pode ver aqui é todo o resto no entanto tem um uma parte desses conjuntos que a gente chama de parcialmente decidíveis é O que é a utilização de uma máquina de turing e elas e essa máquina de turing sempre vai parar para dizer sim mas para dizer não ela
pode não parar tá Então imagina se eu pergunto se essa garrafa aqui pertence a um determinado especificação E se ela pertence é a máquina de tudo E sempre vai parar e vai falar sim pertence essa especificação no entanto a vamos supor que essa garrafa que não pertence a essa especificação essa minha máquina de turing pode parar para dizer não mas ela também pode rodar indefinidamente tá e esse é um problema é semi decidível ou parcialmente decidiu a porque essa essa não é essa máquina de turing pode não parar e aí eu tenho a todos os
outros E aqui nessa nesse interno desse quadrado aqui só inclusive incluindo os problemas que você não garante Nem que a máquina de turing vai parar para dizer sim nos casos positivos tá então esses são problemas não decidíveis ver como que a gente prova com um problema não é decidível então vamos supor que você tem algum sei lá você trabalha na empresa e seu chefe quer resolver um problema otimização de produção de um trabalho na na fábrica de automóveis ele chega um problema para você e você quer resolver esse problema mas talvez seja um problema tão
difícil que ele não seja nenhum problema decidível e a invés de bater cabeça por três meses recebendo o salário tentando resolver um problema aqui não é resolvi não é decidível talvez você pode identificar que ele não é decide e se você pouca todo esse trabalho hoje tentar resolver esse problema e como que eu posso provar que um problema não é decidível o método você pode No mínimo você tem duas formas de fazer isso A primeira é provando diretamente ó por a mais ver aqui eu tô provando que esse problema não é decidido ou você pode
utilizar redução de problemas que que a redução de problema é quando você a e agora você tem problema Esse problema você já sabe que ele não é decidível Oi e aí você o problema que você quer provar você reduz ele a esse primeiro problema que você já sabe que não é decidiu se você conseguir o reduzir vamos vamos vamos dar nomes aos bois você tem um problema a que você sabe que não é decidível e você quer provar para um problema b não é decidível a basta você reduzir o problema de E qual o problema
se você conseguiu reduzir o problema Bial programar significa que o problema é bebê também não é decidível tá E aí você facilita o processo privacy esse processo de redução é mais simples do que você conseguir a provar diretamente um problema decidi Vou não mas a gente vai fazer uma prova aqui agora é de um problema que não é decidível
