Problemas Decidíveis e Problemas indecidíveis: �

O Legado de �Alan Turing�

Ruy J.G.B. de Queiroz

Problemas Indecidíveis

� Imagine o desafio de ter que mostrar que um dado problema da Matemática é insolúvel!

� Em 1936 Alan Turing veio com uma definição precisa de máquinas idealizadas: a máquina de Turing. Isso viabilizou a definição exata da decidibilidade de problemas matemáticos, e, portanto, abrindo a possibilidade de se demonstrar que certos problemas são de fato indecidíveis.

� Efeitos colaterais:

(1) definição matemática de programa;

(2) concepção de computador de programa armazenado.

Problemas Geométricos

� Já na Grécia antiga, os matemáticos buscavam por construções para trissectar um dado ângulo, assim como por construções para transformar um círculo num quadrado de mesma área.

Trissectar com régua e compasso

� Somente em 1837, o matemático francês Pierre Wantzel (1814-1848), mostrou que não existe método geral para trissectar um ângulo usando apenas régua-e-compasso.

� A estratégia de Wantzel foi se valer da chamada teoria de Galois -- mais especificamente, a trissecção de um ângulo corresponde à resolução de uma certa equação cúbica, que não é possível usando as ferramentas dadas.

Outros resultados de Wantzel

� No mesmo artigo em que demonstrou a impossibilidade de trissectar um ângulo, Wantzel também demonstrou a impossibilidade de, usando apenas régua-e-compasso: 1.  Dobrar o cubo 2.  Construir um polígono regular com certa

característica

Dobrar o Cubo

� dobrar o cubo: significa ser capaz de, ao receber um dado cubo de comprimento de lado s e volume V = s3, construir um novo cubo, maior que o original, de volume 2V, e, portanto, comprimento de lado s 3√2.

Construir Polígono Regular

� construir um polígono regular cujo número de lados não é o produto de uma potência de 2 e nenhum número de primos de Fermat distintos.

Quadratizar o Círculo

�  Quadratizar o círculo é um problema proposto pelos geômetras da Antiguidade. Trata-se do desafio de construir um quadrado com a mesma área que um dado círculo, usando apenas régua e compasso.

�  Em 1882, o problema foi demonstrado impossível de resolver, e isso veio como uma conseqüência do teorema de Lindemann–Weierstrass que mostra que � é um número transcendental, e não algébrico.

Fórmula para Achar Raízes de Equações

� Somente em 1824, o matemático norueguês Niels Abel (1802–1829) obteve o importante resultado de que não pode haver uma fórmula (finita) geral, envolvendo apenas operações aritméticas e raízes, que exprima as raízes de um polinômio de grau 5 ou mais em termos de seus coeficientes.

Problema de Decisão

� Um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não. Por exemplo, o problema: "dados dois números x e y, y é divisível por x?" é um problema de decisão.

� Ou ainda: "Dado um número inteiro x, x é um número primo?"

Problema Indecidível

� Uma família de problemas com respostas SIM/NÃO é dita indecidível se não existe algoritmo que termine com a resposta correta para todo problema da família.

�  (Exemplo: 10o problema de Hilbert)

Provar Indecidibilidade

� Para tornar o significado de indecidível preciso, é necessário dispor de uma noção formal de algoritmo.

� Tal noção foi introduzida por Alonzo Church (1936) e Alan Turing (1936) independentemente.

Origens de “Algoritmo”

�  Abu Abdallah Muhammad ibn Musa al-Khwarizmi (c. 780 – c. 850) foi um matemático e astrônomo persa responsável pela introdução no Ocidente dos numerais arábicos, baseado no sistema de numerais indo-arábico desenvolvido na matemática indiana.

Definição de “Algoritmo” (Wikipedia)

�  ”Um algoritmo é um procedimento passo-a-passo com o fim de realizar cálculos, processar dados, automatizar o raciocínio dedutivo.”

�  ”Mais precisamente, um algoritmo é um método eficaz, expresso como uma lista finita de instruções bem definidas para o cálculo de uma função.

�  A partir de um estado inicial e uma entrada inicial (possivelmente vazia), as instruções descrevem uma computação que, quando executada, irá prosseguir por meio de um número finito de estados sucessivos bem definidos, acabando por produzir uma ‘saída’ e terminando em um estado final.”

Algoritmo de Euclides

� O algoritmo de Euclides é um método eficiente de calcular o máximo divisor comum (MDC) de dois números inteiros.

� Presente nos livros VII e X dos Elementos de Euclides (c. 300 a.C.), trata-se de um dos mais antigos algoritmos numéricos que se conhece.

O Décimo Problema de Hilbert

�  Em sua lista de 1900 dos 23 problemas mais importantes da Matemática, David Hilbert incluiu:

10. Determinação da solubilidade de uma equação Diophantina. Dada uma equação Diophantina com qualquer número de quantidades indeterminadas e com coeficientes integrais racionais: Conceber um processo conforme o qual pode ser determinado, em um número finito de operações, se a equação é solúvel nos inteiros racionais.

Generalizando: O Entscheidungsproblem

�  O Entscheidungsproblem (“problema de decisão”, em alemão) é um desafio posto por David Hilbert em 1928.

�  O Entscheidungsproblem pede por um algoritmo que receberá como entrada uma descrição de uma linguagem formal e um enunciado matemático na linguagem, e produzirá como saída “Verdadeiro” ou “Falso”.

�  Tal algoritmo seria capaz de decidir, por exemplo, se enunciados tais como a conjectura de Goldbach ou a hipótese de Riemann, são verdadeiras, muito embora nenhuma prova ou refutação desses enunciados seja conhecida.

Processo Finito

� Em 1928 Hilbert enuncia o Entescheidungsproblem assim:

O Entscheidungsproblem é resolvido quando conhecemos um procedimento que permite, para qualquer expressão lógica dada, decidir sua validade ou satisfatibilidade.

David Hilbert e Problemas Insolúveis

(1900 e 1930)

� “Para o matemático não existe o Ignorabimus [“Ignoramos e ignoraremos”, 1872], e, na minha opinião, de forma alguma para as ciências naturais . . . A verdadeira razão por que [ninguém] conseguiu encontrar um problema insolúvel é que, na minha opinião, não existe problema insolúvel. Em contraste com o Ignorabimus, nosso lema será: Temos que saber, Saberemos.”

Busca por uma Definição

� No período de 1928 a 1936, Emil Post trabalhou intensamente no desenvolvimento de uma definição do que seria procedimento envolvendo um número finito de passos: um trabalhador se movendo de sala em sala escrevendo e apagando símbolos conforme uma lista de instruções.

Formalização de Algoritmo

�  Naturalmente, antes que a questão da solubilidade do Entscheidungsproblem pudesse ser resolvida, a noção de algoritmo tinha que ser formalmente definida.

�  Coube a Alonzo Church em 1936 com o conceito de calculabilidade efetiva baseado no seu �-cálculo, e a Alan Turing também em 1936, com a noção de máquina de Turing.

Tese de Church-Turing

� Em seu artigo de 1936 (publicado em 1937, e avaliado por Church) Turing acrescentou um apêndice demonstrando que a classe de funções computáveis pelo �-cálculo era a mesma que a classe de funções computáveis por máquinas de Turing.

� Daí, a denominação Tese de Church–Turing: toda função computável é computável por máquinas de Turing.

Limitação do Homo Sapiens

�  “Na verdade, o trabalho feito por Church e outros leva essa identificação consideravelmente além do estágio de hipótese de trabalho.”

�  “Porém, mascarar essa identificação sob uma definição esconde o fato de que uma descoberta fundamental nas limitações do poder de matematicatização do Homo Sapiens foi feita, e nos cega para a necessidade de sua contínua verificação.” (Emil Post)

Turing encara desafio

� Na primavera de 1935 Turing, ainda como aluno de Mestrado no King’s College (Cambridge, UK), aceitou o desafio de provar que não haveria processo ‘mecânico’ que resolvesse o Entscheidungsproblem.

� O estímulo veio do matemático Max Newman, orientador de Mestrado de Turing, num curso sobre os Fundamentos da Matemática.

Robin Gandy (colega)

�  “À pergunta ‘o que é um processo “mecânico”?’ Turing dá a resposta característica ‘Algo que pode ser feito por uma máquina’, e aí embarca na tarefa altamente congênere de analisar a noção geral de uma máquina de computação.”

Entscheidungsproblem: Impossível

� Muitos acreditavam que seria impossível haver um algoritmo para decidir toda questão da Matemática, entre eles o matemático G.H. Hardy (1877–1947), de Cambridge:

G.H. Hardy e o Entscheidungsproblem

�  “Não há, obviamente, nada disso [algoritmo], e isso é muito bom, pois se houvesse teríamos um conjunto mecânico de regras para a solução de todos os problemas matemáticos, e nossas atividades como matemáticos chegaria ao fim.”

Turing e o Entscheidungsproblem

�  “Suponho, porém não tenho certeza, que Turing, desde o início de seu trabalho, tinha como objetivo uma prova da indecidibilidade do Entscheidungsproblem.”

�  “A ‘idéia principal’ pode ter sido sua análise do fenômeno da computação ou sua percepção de que havia uma máquina universal, e portanto um argumento diagonal para provar a insolubilidade.” (Robin Gandy, 1974)

Máquina de Turing

Definição Matemática

�  Uma máquina de Turing é uma 7�upla, (Q,�,�,�,q0,qaceita,qrejeita), onde Q,�,� são todos conjuntos finitos, � é a função de transição, q0 � Q é o estado inicial, qaceita é o estado de aceitação, e qrejeita é o estado de rejeição. (Pode ser codificada numa palavra finita, e, portanto servir como entrada para outra máquina)

�  Trata-se de um modelo formal de um “ser humano calculante”: cada célula da fita de trabalho pode ser concebida como uma folha de papel, � como o alfabeto de entrada, e � o alfabeto de trabalho.

Alan Turing: Máquina Universal

� “É possível inventar uma única máquina que pode ser usada para computar qualquer seqüência computável.”

� “Se essa máquina U for alimentada com a fita no começo da qual está escrita a cadeia de quíntuplas separadas por vírgulas de alguma máquina de computação M, então U vai computar a mesma seqüência que M.”

Martin Davis sobre a Máquina Universal

�  “As pessoas já vinham pensando em máquinas de computar há um bom tempo, desde a época de Leibniz e até antes disso.

�  Antes de Turing, a suposição geral era de que, ao lidar com tais máquinas, as três categorias, máquina, programa, e dados, eram entidades totalmente separadas. A máquina era um objeto físico; o que hoje chamaríamos de hardware. O programa era o plano para realizar uma computação, talvez encorpado em cartões perfurados ou conexões de cabos num quadro. Finalmente, os dados eram a entrada numérical.

�  A máquina universal de Turing mostrou que a distinção dessas três categorias é uma ilusão”

Implementação da Máquina Universal

�  “Em 19/02/1946 Turing apresentou um artigo detalhado ao comitê executivo do National Physical Laboratory (NPL), dando o primeiro design razoavelmente completo de um computador de programa armazenado: o Automatic Computing Engine.”

�  “O mais conhecido design do EDVAC apresentado no relatório First Draft of a Report on the EDVAC (30/06/1945), de John von Neumann, que conhecia o trabalho teórico de Turing, teve muita divulgação, apesar de seu estado incompleto e ausência questionável de atribuição das fontes de algumas das idéias.” (Wikipedia)

John von Neumann em 1948

�  “Um autômato é "universal” se qualquer seqüência que possa ser produzida por qualquer que seja o autômato também pode ser resolvida por esse autômato específico.”

�  “Turing observou que uma descrição completamente geral de qualquer autômato concebível pode ser (no sentido da definição anterior) dada em um número finito de palavras.”

�  (“The General and Logical Theory of Automata”, Setembro 1948)

Problemas Decidíveis

1.  Determinar se um sistema de equações lineares em k variáveis, com coeficientes em Z, têm soluções em Z.

2.  Determinar quais equações da forma x2 � dy2 = 1, onde d é um inteiro positivo, têm soluções nos inteiros.

3.  Determinar para qual(is) valor(es) inteiro(s) de k a equação y2 = x3 + k tem solução nos inteiros. (Alan Baker, Medalha Fields 1996)

Problema Indecidível

�  Em 1900, Hilbert pediu em seu décimo problema:

Encontrar um algoritmo para decidir se um sistema de equações com coeficientes inteiros tem uma solução inteira.

�  Somente em 1970, surgiu uma resposta: o russo Yuri Matejasevic, então com 23 anos de idade, demonstrou que não pode haver tal algoritmo (assumindo a Tese de Church–Turing).

Subproduto do 10o Problema

�  O conjunto de valores positivos tomados pelo polinômio (em 26 variáveis):

(k+2)(1�(wz+h+j�q)2 �((gk+2g+k+1)(h+j)+h�z)2� (16(k+1)3(k+2)(n+1)2 +1�f2)2 �(2n+p+q+z�e)2� (e3(e+2)(a+1)2 +1�o2)2 �((a2 �1)y2 +1�x2)2� (16r2y4(a2 �1)+1�u2)2 �(n+l +v �y)2� ((a2 �1)l2 +1�m2)2 �(ai +k +1�l �i)2� (((a+u2(u2 �a))2 �1)(n+4dy)2 +1�(x +cu)2)2� (p+l(a�n�1)+b(2an+2a�n2 �2n�2)�m)2� (q+y(a�p�1)+s(2ap+2a�p2 �2p�2)�x)2� (z+pl(a�p)+t(2ap�p2 �1)�pm)2)

é exatamente o conjunto dos números primos!

Problema Decidível

� Em 1930, (embora publicado apenas em 1948), o lógico polonês Alfred Tarski demonstrou que:

Existe um algoritmo para testar a solubilidade, nos reais, de sistemas de equações polinomiais com coeficientes inteiros.

Problema Indecidível (Turing)

�  Turing mostrou que o problema de se determinar se uma dada máquina de Turing pára ou não quando roda sobre uma dada entrada é indecidível.

�  Esse ficou conhecido como o Problema da Parada.

�  Trata-se de um problema matemático de decisão, que não tem solução, daí o Entscheidungsproblem, que é o caso mais geral, também não tem solução

Referencial para outros Problemas

� Várias outras demonstrações de indecibilidade, inclusive a de Emil Post (1946) com relação ao problema da correspondência, passaram a utilizar como referencial o Problema da Parada:

se esse problema for decidível então o Problema da Parada também o é, portanto ele não pode ser decidível.

Problemas Indecidíveis na Computação

1.  Determinar se dois programas são equivalentes.

2.  Determinar se uma gramática livre-do-contexto é ambígüa.

3.  Determinar se duas gramáticas livres-do-contexto são equivalentes.

4.  Determinar se duas expressões do �-cálculo são equivalentes.

5.  Determinar se uma dada expressão do �-cálculo tem forma normal.

Problemas Indecidíveis da Matemática

Combinatória: ladrilhamento, desigualdades lineares entre densidades de homomorfismo de grafos

Semigrupos de matrizes: problema da mortalidade de matrizes, problema da palavra

Topologia: problema do homeomorfismo, detecção de variedade

Teoria dos números: problema de decisão para a teoria de 1a. ordem dos racionais

Teoria dos nós: determinar se um nó n-dimensional está desatado (n>2)

Análise: existência de soluções para equações diferenciais algébricas

Sistemas dinâmicos: ponto vai para a origem em tempo finito? problema Collatz generalizado

Probabilidade: estabilidade de caminhadas aleatórias

Geometria algébrica: existência de seções racionais

A Noção de Oráculo

�  Em 1939, com o objetivo de introduzir o conceito de máquina de Turing não-determinística, Turing define a noção de máquina oráculo, que permitiu a classificação de problemas em termos de computabilidade relativa.

�  O grau de Turing ou grau de insolubilidade de um conjunto de números naturais mede o nível de insolubilidade do conjunto.

Custo Computacional

�  Dentre os modelos matemáticos do conceito de algoritmo, a máquina de Turing tem servido de referencial teórico para a classificação de algoritmos e problemas segundo os respectivos requisitos de recursos necessários:

1.  Tempo: medido pelo número de passos de computação

2.  Espaço: medido pelo número de células da fita de trabalho utilizadas

Solubilidade na Prática

Classes de Complexidade de Problemas Computacionais:

1.   P: problemas solúveis por uma máquina de Turing determinística de tempo polinomial

2.   NP: problemas solúveis por uma máquina de Turing não-determinística de tempo polinomial (ou conferíveis por uma máquina de Turing determinística de tempo polinomial).

Legado na Criptografia Moderna

1.  Definição de: função unidirecional, função pseudoaleatória, indistinguibilidade

2.  Definição da noção de experimento, permitindo a definição matemática de:

�  sigilo computacional, resistência à colisão, inforjabilidade existencial

3.  Provas de segurança relativa (por redução)

Legado na Inteligência Artificial

�  Em 1950, Turing procura uma resposta científica à pergunta:

Máquinas podem pensar?

�  Jogo da Imitação: humano conversando, por meio de terminal, com uma máquina e um humano, sem saber quem é a máquina, pretende distinguí-los, podendo fazer qualquer tipo de pergunta a cada um deles, cuja resposta pode ou não ser verdadeira.

Distinguir uma Máquina de um Humano

�  A resposta à pergunta se a máquina pode pensar será respondida na afirmativa se ela puder imitar um ser humano nas suas respostas. Aplicação nos dias de hoje: Completely Automated Public Turing test to tell Computers and Humans Apart (CAPTCHA)

�  Teste de desafio cognitivo, utilizado como ferramenta anti-spam, desenvolvido pioneiramente na Universidade Carnegie-Mellon (Luis von Ahn).

Teste de Turing Reverso

Humanos seriam Máquinas?

� Turing substitui a pergunta “Máquinas pensam?” por “Máquinas podem fazer o que nós (como entidades pensantes) podemos fazer?”

� A vantagem, segundo Turing, é que delimita “razoavelmente bem as capacidades físicas das capacidades intelectuais de um ser humano.”

Jogo da Imitação

�  “Turing especulou que até o ano de 2000, “um interrogador médio não terá mais do que 70 por cento de chance de fazer a identificação correta” – ou seja, computadores enganariam os juízes 30 por cento das vezes.”

�  “Por anos, sua previsão não se materializou, visto que os sistemas de software não conseguiram se equiparar em inteligência com seus interrogadores humanos.” (Dan Falk, The Guardian, 21 Ago 2012)

“Turing test marathon” (23 Junho 2012)

�  Organizada pela University of Reading como parte das comemorações centenárias do nascimento de Turing– e realizada, apropriadamente, no Bletchley Park em Buckinghamshire, onde ele desempenhou um papel fundamental na quebra do código da Enigma como parte dos esforços de quebra de códigos das Forças Aliadas.

�  30 juízes conversando eletronicamente com 25 “humanos escondidos” (abrigados numa sala adjacente) e cinco “chatbots” sofisticados – programas de computador projetados para imitar a inteligência e a capacidade humanas de conversar.

Maratona de Teste de Turing

�  Algo como 150 conversações separadas foram realizadas.

�  O programa vencedor, desenvolvido por uma equipe russa, se chamava “Eugene”.

�  Tentando emular a personalidade de um garoto de 13-anos de idade, Eugene enganou os juízes 29,2 por cento do tempo, uma margem minimamente inferior ao limiar de 30 por cento de Turing.

Turing sobre Consciência

�  “Não quero dar a impressão de que eu acho que não existe mistério em torno da consciência.”

�  “Há, por exemplo, algo de um paradoxo relacionado a qualquer tentativa de localizá-la.”

�  “Mas não acho que esses mistérios necessariamente precisam de ser resolvidos antes que possamos responder à questão com a qual estamos preocupados neste artigo.”

A Quarta Revolução Tecnológica

�  Nicolau Copérnico: não estamos no centro do universo

�  Charles Darwin: não somos animais superiores e totalmente desconectados dos outros animais

�  Sigmund Freud: não somos seres totalmente racionais

�  Alan Turing: não somos seres autônomos, mas sim inforganismos (segundo Luciano Floridi, Filosofia da Informação), Ou: não somos ilimitados no plano das idéias

The Philosophy of Information, Luciano Floridi (2011)

Referências Bibliográficas

�  Turing, A.M. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society 2 42: 230–65. 1937.

�  Turing, A.M. (1950). “Computing Machinery and Intelligence”. Mind LIX (236): 433–460.

�  Macintyre, A. (2011). “Undecidable and Decidable Problems in Mathematics: A survey and some reflections, for the centenary of Turing’s birth”. Talk given Tuesday, 17 May 2011 - 6:00pm, Barnard’s Inn Hall, Gresham College, London, UK.