MÁQUINAS DE TURING e o Problema da Parada

o princípio que tá por trás dos computadores modernos que todos nós usamos e amamos foi criado nos anos 30 do século passado para resolver Não exatamente um problema matemático mas um problema profundo da própria matemática hoje nós vamos falar sobre máquinas de touring e o problema da parada Olá meu nome é Daniel Nunes você está no tem ciência e o assunto de hoje começa com uma reflexão filosófica de como a matemática funciona ou deveria funcionar na visão dos formalistas Essa era uma visão predominante da matemática na virada pelo século 20 e o seu principal defensor

era o matemático mais famoso da época David Hilbert a visão do Hilbert tem suas raízes nas ideias de Tales de Mileto que viveu na Grécia antiga por volta de 600 antes de Cristo para eles e também para boa parte da comunidade matemática moderna a matemática deve ser pensada como um sistema dedutivo que parte de alguns princípios gerais chamados de axiomas axiomas são os pontos de partida eles são verdades por definição os teoremas matemáticos por outro lado só são verdadeiros Se puderem ser aprovados através da lógica partindo dos axiomas Isso significa que começando nos excecionas um

raciocínio dedutivo estabelece o teoremas ou seja eles são consequências dos axiomas exatamente dessa maneira que as teorias matemáticas são apresentadas o formalismo do Hilbert dissecar desse jeito de pensar imaginava a matemática como um conjunto de símbolos e de regras para manipular esse símbolos não existe nenhum compromisso dessas coisas terem algum significado no mundo real é como num jogo Pensa num jogo de xadrez cada peça se comporta como um símbolo e os movimentos permitidos para cada uma delas seriam as regras usando esse mesmo tabuleiro mas com peças e regras diferentes a gente pode chegar num outro

jogo Como por exemplo o jogo de damas e assim é com as diferentes teorias matemáticas cada uma delas com o seu conjunto de axiomas então uma verdade matemática não é necessariamente uma coisa absoluta mas sim uma verdade dentro de um sistema de axiomas é o que acontece por exemplo com os diferentes tipos de geometria que partem de axiomas diferentes e produzem verdades diferentes no final da década de 1920 estava preocupado com três perguntas filosóficas a respeito da Matemática primeiro a matemática seria completa ou seja toda a proposição verdadeira de um sistema matemático Pode Ser aprovada

a partir dos axiomas desse sistema segundo a matemática seria consistente ou seja esse sistema seria livre de contradições O que significa que não existe uma proposição nele que possa ser provada verdadeira e falsa ao mesmo tempo dentro do sistema e terceiro a matemática é decidível qualquer proposição matemática pode ser avaliada no sistema ou seja existe um algoritmo que pode sempre determinar quando uma proposição segue ou não dos axiomas as duas primeiras perguntas foram respondidas por Craft General Inclusive eu fiz um vídeo recente aqui no canal sobre isso o link está na descrição mas fica o

alerta de que é possível que você tem uma Crise existencial com ele assistir por sua conta em risco já o vídeo de hoje vai focar na terceira pergunta de Wilbert a matemática é decidível essa pergunta é muito importante porque ela indaga-se é possível ao menos Teoricamente ter um método de checar se uma proposição é ou não é consequência dos axiomas de um sistema se a matemática for decisível isso significa que por exemplo partindo dos axiomas de piano é possível dizer se uma certa proposição matemática relacionada com aritmética pode ser provada ou não a partir dos

axiomas por outro lado se a matemática não for decidível então é possível que a gente encontra uma proposição na aritmética de piano que não podemos dizer se segue ou não dos axiomas ou seja ela é indecisível essa terceira pergunta de realmente correspondida alguns anos depois das duas primeiras e quem fez isso foi Alan turing e para responder essa pergunta de filosofia matemática o tule simplesmente inventou as bases da teoria moderna de computação isso faz todo sentido porque se a gente tem um conjunto de axiomas e os teoremas são deduções lógicas a partir deles o processo

de provar teoremas poderia ser reduzido a uma tarefa simples capaz de ser desempeada por um computador ao menos em teoria então entender como o computador funciona é a chave desse mistério só que naquela época não existiam ainda os computadores como hoje computar fazer contas era uma tarefa desempenhada ainda por seres humanos contas complexas e tediosas eram realizadas por pessoas principalmente por mulheres então o touring precisou imaginar como que o ato de computar poderia ser desempenhado através de uma máquina hipotética que não teria as limitações de um ser humano assim ele poderia investigar os limites de

até onde a computação realmente poderia chegar no artigo publicado em 1936 Alan turing inventou um conceito que ficou conhecido depois como máquina de Turim é um modelo teórico que explica o funcionamento de todo tipo de computador moderno de todo tipo de algoritmo é o contrário do que você possa imaginar é um modelo extremamente simples e é o seguinte uma máquina de turing É um mecanismo que tem como uma fita infinita de células com símbolos que são retirados de um conjunto finito o alfabeto da máquina a máquina tem um leitor capaz de ler uma célula por

vez e um programa interno que diz em qual estado ela está e o que fazer a partir desse estado e da Leitura obtida nesse ponto a máquina pode fazer uma das seguintes tarefas ela pode reescrever um novo valor na fita tocando um símbolo pelo outro ela pode se mover para direita ela pode se mover para esquerda ou então ela pode parar o que significa que o programa chegou ao fim da sua execução e o output é justamente a forma final da fita depois do programa parar ela é a resposta que o programa retorna a partir

do impulso Inicial Agora pode acontecer também do programa não parar nunca ele pode ficar preso num loop ou então seguir sua execução indefinidamente sem jamais parar para enxergar isso vamos pensar no seguinte programa com símbolo zero um ele é zero a máquina anda para direita se ele chega Numa célula vazia uma para então sua input for uma sequência de três zeros a máquina vai andando para direita e no final ela para por outro lado se a sequência for 001 a máquina vai ficar presa no looping e nunca para uma máquina de touring Pode parecer excessivamente

simples mas na verdade é que tudo que um computador pode fazer pode ser imaginado como uma máquina de turing suficientemente complexa mas não é só isso a ideia de que uma máquina de turing pode parar ou não é a chave para resolver esse problema da decidibilidade da matemática e essa foi a motivação do true para criar esse conceito por exemplo imagine a conjectura de Gold bar Ela diz que todo número par maior do que dois pode ser escrito com uma soma de dois números primos que a conjectura for falsa então é porque existe um número

par maior que dois que não pode ser escrito como a soma de dois prêmios a falsidade da conjectura de gol de bar poderia ser provado usando uma máquina de turing o programa dessa máquina começaria em quatro e testaria se ele pode ou não ser escrito como a soma de primos quando a máquina encontra uma soma que dá certo ela passa para o números par seguinte para cada número existe uma quantidade finita de formas dele poder ser escrito como a soma de dois inteiros positivos então o programa só precisa fazer um número finito de verificações para

decomposição de cada número par se encontrar ao menos uma decomposição como a soma de dois prêmios a máquina passa pelo número par seguinte mas se ela chegar num número par que não possuem nenhuma decomposição como soma de dois primos então a máquina em treino output Gold by é falsa e para se é conjectura de gol de bar for falsa então essa máquina de turing irá parar sua execução Em algum momento mas alguma leitura for verdadeira então ela não vai parar nunca e aqui vem a grande ideia do Torre E se existir uma máquina de tour

incapaz de receber qualquer programa como seu input e sempre dizia se esse programa irá para ou não a sua execução diante um tempo finito encontrar uma máquina de Two em dessas é resolver o chamado problema da parada se realmente existir uma máquina assim então a gente poderia colocar nela o programa que verifica a conjectura de Gold bar se a máquina disser que o programa para com tua conjectura é falsa mas se ela disser que o programa nunca para então a conjectura é verdadeira portanto Se pudermos resolver o problema da parada resolvemos também um problema da

conjectura de golgá e não é só isso resolveu o problema da parada resolve também o problema da decidibilidade da Matemática porque para ver se uma certa proposição é ou não é consequência de um grupo de axiomas a gente poderia pensar na seguinte máquina de Torre ela parte dos exaxiomas escreve todas as sentenças matemáticas que seguem deles em um único passo lógico depois ela escreve todas as sentenças que seguem em um único passo a partir dessas anteriores e por aí vai a cada nova etapa a máquina checa se algumas dessas sentenças é a proposição que estamos

querendo testar se for a máquina para se não for ela continua a sua execução Então se a gente pegar o programa dessa máquina E colocar na máquina de tour em que resolve o problema da parada caso ela informe que a execução termina é porque a nossa proposição segue dos axiomas Sem informação Ford que o programa Nunca Termina é porque a nossa proposição não é consequência dos axiomas Portanto o problema da parada e a questão da decidibilidade na matemática estão intimamente relacionados em máquina de turing esse problema é são equivalentes então resolveu o problema da parada

é resolver o problema da sensibilidade e o Turim conseguiu fazer isso mas como é que ele fez ele imaginou o que aconteceria caso o problema da parada tivesse uma solução positiva ou seja existe isso uma máquina de True incapaz de verificar em tempo finito se o programa com certo impulso iria parar ou não vamos chamar uma máquina assim de ter para testar se uma máquina de Three m com certo input vai parar ou não a gente pega o programa de m esse input insere na máquina T cm parar Então a máquina T diz que m

para se M não parar Então a máquina T diz que M não para a gente pode modificar ter acoplando ela a um outro programa que faz o oposto de ter isso gera uma máquina maior tem mais que funciona da seguinte maneira pegamos um programa m e seu input e colocamos na máquina Primeiro ela roda o programa T caso o output de T seja que m para então ter mais produz um looping caso o output de T seja que M não para então tem mais para o pulo do gato é fazer ter mais rodar o seu

próprio programa como input CT concluir que ter mais para então tem mais vai fazer o oposto entrar em looping por outro lado se ter concluo que tem mais não para então tem mais também faz o oposto e para ou seja em qualquer situação Acontece uma contradição da sempre errado e a Razão de isso acontecer é que uma máquina como ter não pode existir ou seja o problema da parada tem solução negativa não existe uma maneira em geral se uma máquina de touring vai parar ou não para um dado input e como o problema da parada

Tem Resposta negativa meus amigos o problema ela decidibilidade também é negativo a matemática é indecisível existe sistemas matemáticos que possuem proposições que não podem ser verificadas dentro desse sistema em outras palavras não existe um algoritmo capaz de determinar sempre se uma proposição segue ou não dos axiomas do sistema em princípio tudo aquilo que é computável poderia ser feito por uma máquina de Torre se uma máquina de Twin não pode computar então a coisa não é computar essencialmente máquina de True são um limite teórico para os computadores até hoje os melhores sistemas computacionais são aqueles que

podem fazer tudo que uma máquina de turing pode são chamados sistemas turing completos Então nesse sentido as máquinas de túneis são a base da Computação moderna durante a Segunda Guerra Mundial que o reconstruiu máquinas reais para ajudar a quebrar nazistas e depois da guerra Turim e fonoaium projetaram o primeiro computador programável real um Eniac o cara dominava teoria e a prática É incrível como que tudo isso começou na tentativa de responder a uma pergunta extremamente teórica feita pelo Wilbert a respeito da matemática e esse é mais um bom argumento para rebater a pergunta qual a

aplicação disso quando alguém fala com desdém da Matemática inclusive muitas dessas falam feitas através de dispositivos como esse que você tá usando agora e que tem as suas origens numa matemática bastante abstrata então Toda vez que você usar um computador um celular um videogame um relógio Smart etc lembra que essas coisas todas só estão aqui porque um dia Alan turing queria refletir a respeito de uma pergunta bem teórica a matemática é decidível Muito obrigado aos membros do canal E não se esqueça de deixar o like se inscrever e até o próximo vídeo [Música]