O mal-entendido zumbi da ciência da computação teórica

• Na ciência da computação teórica, computabilidade e NP-hard são conceitos aplicados a funções, linguagens e sequências infinitas, não a inteiros individuais nem a perguntas isoladas de verdadeiro/falso
• No exemplo de Sipser, “a função f que sempre retorna 1 se Deus existe e sempre retorna 0 caso contrário” é uma função constante em ambos os casos, portanto é computável
• P vs NP não é um problema que recebe entradas, mas uma única pergunta de sim/não; por isso, não pode ser chamado, em si, de NP-hard nem de incomputável
• A função Busy Beaver como um todo é incomputável, mas um valor específico como BB(6) não pode ser tratado da mesma forma, já que, para qualquer inteiro k, existe um programa print k
• O núcleo da confusão recorrente está em aplicar conceitos destinados a objetos infinitos a problemas individuais, e o hábito de misturar a incomputabilidade do problema da parada com a incompletude de Gödel pertence à mesma família

---

O alcance da computabilidade que o exemplo de Sipser ensina

• Em Introduction to the Theory of Computation, de Michael Sipser, há um exercício que evidencia a definição de computabilidade
  • Seja f:{0,1}*→{0,1} a função que sempre retorna 1 se Deus existe, e sempre retorna 0 se não existe
  • A pergunta é se f é computável, e a resposta independe de crença religiosa
• f é computável
  • A função constante que sempre retorna 1 é computável
  • A função constante que sempre retorna 0 também é computável
  • Se f é uma das duas, então f também é computável
• Uma pergunta paralela com a mesma estrutura dá a mesma intuição
  • Na pergunta “se Deus existe, n=3; caso contrário, n=5; n é primo?”, mesmo que n não esteja totalmente especificado, basta saber que ele é um elemento de {3,5} para dizer que é primo
  • Com f ocorre o mesmo: só muda qual função constante ela é, mas ela está especificada o suficiente para ser julgada computável

Computabilidade é existência, não dificuldade de escrever um programa

• Computabilidade é um conceito aplicado a funções ou sequências infinitas
• Não se atribui computabilidade da mesma forma a perguntas individuais de sim/não ou a inteiros individuais
• A pergunta central é se existe um programa de computador que mapeia entradas para saídas
• O quão difícil é escolher, descobrir ou escrever esse programa não faz parte da definição de computabilidade
  • Mesmo que escrever o programa exigisse resolver a existência de Deus, a avaliação de computabilidade em si não mudaria

Por que P vs NP não pode ser chamado de NP-hard

• A pergunta “a própria questão P versus NP é NP-hard e, por isso, insolúvel?” se repetiu várias vezes nos últimos 25 anos
• NP-hard se aplica a funções ou linguagens que recebem entradas, como 3SAT, Independent Set e Clique
  • A entrada é uma fórmula booleana, um grafo etc.
  • A saída é a resposta para aquela entrada
  • Um problema é chamado de NP-hard quando, se ele puder ser resolvido em tempo polinomial, então, por reduções, todas as linguagens ou funções em NP também poderão ser resolvidas em tempo polinomial
• P vs NP não é uma função nem uma linguagem, mas uma única pergunta de sim/não
  • Não se exclui a possibilidade de que sua resposta seja independente dos axiomas da teoria dos conjuntos de Zermelo-Fraenkel
  • Mas não se pode dizer que essa pergunta em si seja incomputável ou NP-hard
• Formalmente, existe um programa rápido que responde corretamente à pergunta P vs NP
  • Se P=NP, o programa que imprime “P=NP”
  • Se P≠NP, o programa que imprime “P≠NP”

A mesma confusão que se repete no Busy Beaver

• Nos comentários de um texto em que o valor de Busy Beaver 5 foi determinado, perguntas semelhantes se repetiram
  • “Qual é o menor n para o qual o valor de BB(n) se torna incomputável?”
  • “BB(6) já pode ser incomputável?”
• A função Busy Beaver é incomputável
• Mas o conceito de computabilidade não se aplica desse modo a um inteiro individual como BB(6)
  • Seja qual for o inteiro k que venha a ser BB(6), existe um programa print k
  • Esse programa imprime esse inteiro
• Em vez disso, a pergunta que pode ser feita é: para quais n o valor de BB(n) é impossível de provar em um sistema axiomático como a teoria dos conjuntos ZF?
  • Aaronson e Adam Yedidia trataram dessa pergunta em 2016
  • O recorde atual é n=745, uma melhoria sobre o n=8000 de Aaronson e Adam
• Todo inteiro específico pode ser visto como “computável”; o que é incomputável é a função BB como um todo

Por que o “mal-entendido zumbi” continua vivo

• O núcleo da confusão recorrente está em aplicar incorretamente, a inteiros individuais e problemas em aberto, conceitos projetados para sequências infinitas e funções
• Casos que misturam a incomputabilidade do problema da parada com a incompletude de Gödel pertencem à mesma família de confusões
  • As duas coisas estão intimamente relacionadas
  • Gödel permite falar sobre proposições individuais
  • A computabilidade de Turing não é relativa a um sistema axiomático específico, mas um conceito absoluto
• Esta explicação serve como ponto de referência para ser linkado quando o mesmo mal-entendido pedagógico voltar a aparecer
• A pergunta final se volta a como fazer esse mal-entendido “zumbi” descansar

[GN⁺]

Opiniões no Hacker News

• O fato de o conceito de computabilidade inevitavelmente envolver o infinito pode ser bastante contraintuitivo
  Por exemplo, se perguntarmos se existe um algoritmo que calcula a complexidade de Kolmogorov K(s) para uma string arbitrária s, a resposta é, como se sabe, “não”. Não existe uma máquina de Turing que receba strings de comprimento arbitrário como entrada e calcule K(s), e a prova é curta usando o problema da parada
  Mas, se perguntarmos se existe um algoritmo que calcula K(s) para uma string arbitrária s de comprimento menor que n, a resposta é “sim”. Para qualquer n, existe tal algoritmo
  O método, de forma decepcionante, é criar uma máquina de Turing com uma gigantesca tabela de consulta contendo os valores de K(s) para todas as 2^n strings possíveis. Como obter essa tabela na prática é outra questão; uma implementação específica tem descrição finita, e K(s) também é finito para todo s, portanto o algoritmo existe
  Assim, perguntas finitas sobre objetos finitos podem não ser muito interessantes do ponto de vista da computabilidade. Afinal, sempre é possível escrever um programa que imprima todas as respostas; a coisa só fica interessante quando a pergunta se estende a um conjunto infinito de objetos, pois aí surge a questão de saber se algo finito consegue responder a infinitas perguntas

  • Esse tipo de explicação pode fazer uma grande parte da ciência da computação soar como uma brincadeira ridícula e sem sentido
    Na prática, o infinito está servindo como substituto para “o comportamento aproximado, assintótico, de estado estacionário, para N grande o bastante em relação a qualquer truque pontual”
    No mundo real, esses truques também importam, e as constantes e termos de ordem inferior ignorados em comparações Big-O também são importantes para o desempenho real. Há sempre uma tensão entre “problemas grandes o bastante para que fatores constantes deixem de importar” e “problemas pequenos o bastante para caber no intervalo que a palavra constante implica implicitamente”. Um exemplo é quando inteiros de 32 bits fingem ser inteiros
  • Claro que n, por definição, é um número finito, então tal algoritmo existe
    Do ponto de vista do infinito, todo número finito é, na verdade, muito pequeno. Sentado numa cadeira no fim do universo, 1 milha não é diferente de 1 milímetro
    Esse cenário é basicamente algo como “o hotel infinito de Hilbert em cima de um computador”. Se você desloca os programas existentes uma posição, consegue adicionar um novo programa, e o tamanho da tabela necessário para o cálculo permanece o mesmo
    Generalizando mais, a maioria das pessoas tem pouca intuição sobre como funcionam o infinito, os alephs e a matemática transfinita. Eles têm pouca relevância cotidiana e estão profundamente ligados a propriedades emergentes da matemática, da teoria das categorias e da teoria dos conjuntos. Não é só que o infinito seja maior que qualquer número finito; o fato de que alguns infinitos também podem ser maiores que outros infinitos não aparece imediatamente para uma intuição presa ao conceito escolar de “infinito”
    A pergunta mais interessante é se existe algum n < ∞ que torne o algoritmo computável; obviamente a resposta é não, e lá se vai o Prêmio Turing
  • É parecido com o fato de que todos os computadores reais também têm apenas estados finitos, então estão mais próximos de máquinas de estados finitos do que de máquinas de Turing
  • Também se pode dizer que há um algoritmo simples para calcular K(s) para um s específico e, portanto, também para qualquer conjunto finito desses inputs
    A ideia seria enumerar todas as máquinas de Turing possíveis, começando pelas mais curtas, até encontrar uma que imprima s. Se todas as máquinas mais curtas foram testadas e não imprimiram s, então foi encontrada a máquina mais curta que imprime s, logo seu comprimento é K(s). Outras máquinas de mesmo comprimento ou mais longas também podem imprimir s, mas K(s) é o valor referente ao comprimento mínimo, então isso não muda
  • Isso me lembra o poder adicional que P/Poly pode ter em relação a P. Acho que havia um nome geral para a hierarquia de complexidade de circuitos em que o próprio circuito precisa ser gerado por uma máquina de Turing simples, mas não consigo lembrar agora

• Pela minha experiência, aqui a matemática construtivista combina melhor com a intuição das pessoas do que a ciência da computação clássica
  Por exemplo, ainda não existe uma prova construtiva de que haja um programa que imprima a resposta para o problema P=NP
  Também tratei dessa questão no meu artigo em relação a conjuntos de Julia computáveis. Mark Braverman provou que todos os conjuntos de Julia quadráticos são computáveis, mas ele mesmo explica que essa prova não é uniformemente computável. Em vez disso, ele constrói 5 máquinas que recebem os parâmetros do conjunto de Julia desejado e tentam desenhar vários conjuntos na resolução desejada; para cada conjunto de Julia, uma delas desenha corretamente
  Na matemática construtivista, o conceito construtivo de conjunto compacto corresponde aproximadamente ao sentido de conjunto computável necessário para conjuntos de Julia computáveis. Mas não é possível provar construtivamente que todos os conjuntos de Julia quadráticos são compactos; é preciso dividir o plano complexo dos parâmetros possíveis em várias regiões e provar que, dentro de cada região, os respectivos conjuntos de Julia são compactos
  Na matemática clássica, a união dessas regiões é todo o plano complexo, mas, no construtivismo, esse resultado não vale. Da mesma forma, na matemática clássica, a união dos reais positivos com os reais não positivos é toda a reta real, mas, no construtivismo, isso também não vale
  A abordagem construtivista diz exatamente quais informações adicionais são necessárias para realizar o cálculo de fato. Ou seja, é preciso descobrir a qual região do plano complexo pertence o parâmetro dado, para então saber qual das 5 máquinas executar a fim de obter a imagem desejada. Esse me parece um tipo de resposta muito mais satisfatório

  • Mesmo no caso P=?NP citado por Aaronson, a resposta não deveria ser uma resposta clássica como “P=NP”, mas uma função real NP→P
    As pessoas sabem instintivamente que precisam saber em qual lado do desvio estão; elas só não se esqueceram disso por terem sido treinadas em lógica clássica
  • É interessante que “para cada conjunto de Julia, uma das 5 máquinas o desenha corretamente”. Fico me perguntando se isso corresponde essencialmente a uma prova de que a probabilidade de calcular o conjunto correto é de pelo menos 1/5
    Também fico curioso se a pergunta “qual das 5 está certa” é vista como algo para o qual há uma prova ainda não encontrada, ou como algo indecidível, como dentro de ZFC

• Vejo isso como um dos fatores que tornam difícil entender a indecidibilidade do problema da parada.
  Dá vontade de dizer que “existem máquinas tão complexas que nenhuma máquina consegue determinar se elas param ou não”, mas um dos programas triviais return true e return false sempre dará a resposta correta, seja qual for a máquina e a entrada fornecidas.
  Alguém poderia responder: “esses programas não sabem nada sobre máquinas de Turing, então devem ser excluídos”, mas decidibilidade não é sobre isso. Também se poderia pensar que “é indecidível descobrir qual dos dois programas está correto”, mas isso também tem uma resposta determinada como verdadeiro ou falso. O problema só pode se tornar indecidível quando se expande para o conjunto infinito de combinações máquina/entrada.

  • Outros problemas que surgem apenas em famílias de objetos também podem ser igualmente difíceis para iniciantes entenderem.
    Por exemplo, qualquer espaço vetorial de dimensão finita é isomorfo, de várias maneiras, ao seu espaço dual e ao seu bidual; mas, no segundo caso, é possível escolher um isomorfismo “natural” coerente em todos esses espaços, enquanto no primeiro não.
    Daí surgem confusões como: “por que eles não são naturalmente isomorfos? As bases têm o mesmo tamanho! Por que importa se depende da base ou não? Outras demonstrações escolhem uma base; por que lá tudo bem?”

• Acho que o problema da formulação é que ela exige lógica modal.
  “Se Deus existe, defina f:{0,1}*→{0,1} como a função constante 1; se Deus não existe, como a função constante 0. f é computável? Dica: a resposta não depende de crença religiosa.”
  A pergunta correta é se f seria computável, isto é, se existe uma máquina de Turing M tal que, para todo x, f(x)=M(x).
  A resposta é sim. Em qualquer mundo, existe uma máquina de Turing trivial M=1_M ou M=0_M. Por outro lado, a formulação original, “f é computável?”, é uma pergunta modalmente malformada, parecida com uma pergunta gramaticalmente imprecisa como nos paradoxos Sleeping Beauty ou Red Envelope.
  De outro ponto de vista, a dependência de Deus, ou de algum fato que pode ser real, é mais parecida com uma diretiva de compilador ou pragma que será preenchida depois, mas fica determinada antes do uso. Quando se pergunta corretamente, é apenas uma questão de desdobrar as definições rigorosas de função e computabilidade, ambas explicitamente definidas em Sipser.

  • Minha reação foi parecida, e escrevi isso nos comentários do texto de Aaronson. A pergunta não é sobre uma função f capaz de chamar a função constante 1 ou a função constante 0 dependendo de Deus existir.
    A questão é que o referente do rótulo f é a função constante 1 se Deus existe, e a função constante 0 se Deus não existe; nós apenas não sabemos qual das duas é até sabermos se Deus existe. Como a computabilidade das duas funções constantes é óbvia, na prática isso se parece mais com um problema de rótulo do que de computabilidade.
  • Os paradoxos Sleeping Beauty ou Red Envelope não parecem ter muita relação aqui. Eles apenas mostram que aplicar conceitos puramente matemáticos de probabilidade à realidade concreta às vezes não é simples.
    Isso não surpreende, considerando que o próprio fato de a teoria da probabilidade funcionar quando aplicada à realidade é muito misterioso e tem sido objeto de diversas investigações científicas e filosóficas.
    A solução proposta do tipo “would f be” também não parece resolver muita coisa. O objetivo da pergunta sobre “Deus” é fazer o leitor se afastar de um problema P-NP específico e entender que, para funções constantes, o conceito de computabilidade não é útil. Para essa proposta ajudar, ela teria que se aplicar também à pergunta P-NP original, mas ainda não vejo como a abordagem modal entra numa pergunta matemática bem definida.
  • Acho que escrever essa frase um pouco mais por extenso reduziria erros de interpretação.
    “Se Deus existe, defina f:{0,1}→{0,1} como a função constante 1; se Deus não existe, defina f:{0,1}→{0,1} como a função constante 0.”
  • Qualquer que seja o predicado colocado no lugar de “Deus”, a implicação é, rigorosamente falando, verdadeira na lógica clássica de primeira ordem, e provavelmente também em muitos outros sistemas lógicos. A analogia com pragma é adequada.
    Se tal predicado corresponde ao conceito pessoal de Deus de alguém é uma questão não matemática separada.
    É parecido com a surpresa das pessoas ao aprenderem que, na lógica clássica, uma proposição falsa implica qualquer coisa. A matemática tem regras formais rigorosas, e é importante deixar de lado pressupostos sobre os sentidos cotidianos de palavras como “implica” ou “se”.
  • A versão dependente do tempo é muito mais interessante.
    Seria algo como G:t∈ℝ⁺->{0,1}, definido como 1 se Deus existe no tempo t, e 0 caso contrário.
    Claro que analisar G em um referencial não inercial torna tudo ainda mais interessante.

• Sipser está explorando o fato de que a maioria das pessoas não distingue bem computação de investigação empírica.
  “Deus existe?” talvez seja uma pergunta irrespondível, mas esse não é o ponto. Encontrar essa resposta não pertence, para começo de conversa, ao domínio da computação. Computação é apenas um procedimento que mapeia entradas em saídas e, nesse caso, a existência de Deus é uma das entradas.
  A confusão vem do fato de que não podemos saber de fato o valor da entrada, mas o programa ainda existe e é trivial. Poderíamos trocar por outra pergunta empírica binária.
  Por exemplo, suponha que f:{0,1}* -> {0,1} seja “1 se houver pelo menos um banheiro químico em Paris; 0 caso contrário”. Isso é computável e pode até ser executado com a entrada verdadeira. A função sobre Deus também é computável, só que só pode ser executada com uma entrada conjecturada. Mesmo que não se possa garantir que a saída corresponda de modo significativo ao universo em que vivemos, ela ainda é uma função computável.
  Mais simplesmente, podemos considerar apenas f:{0,1}* -> {0,1}. “Deus existe” e “Deus não existe” são, cada uma, strings de bits possíveis. Se a pergunta for se pode existir um programa que, recebendo uma delas como entrada, produza 0, e recebendo a outra, produza 1, a resposta obviamente é sim. Não importa se a entrada é empiricamente verdadeira ou não.

  • Na verdade, as funções da pergunta nem usam a entrada. Poderiam muito bem ser definidas como funções do conjunto vazio para {0, 1}.
    O f da pergunta não é uma função, mas um rótulo. Se Deus existe, o referente de f é f1, que sempre produz 1; se Deus não existe, é f0, que sempre produz 0. Portanto, na prática, não é um problema de computabilidade, mas de rótulo.

• Matemáticos e cientistas da computação sempre acabam fazendo isso porque usam expressões abreviadas, omitindo detalhes para facilitar a conversa.
  Não é diferente de dizer “multiplique os dois lados por dx”. A pergunta “o problema do caixeiro-viajante é NP-difícil?” se refere a uma família de problemas, não a uma instância específica. Se você fixa um grafo específico, não há N, então obviamente ele não é NP-difícil.
  Para quem sabe disso, é tão óbvio que nem vale a pena dizer, mas, para quem não conhece o significado dos termos, fica completamente inacessível.
  Eu também já tive, no passado, um mal-entendido parecido em outra área. Eu via o DNA como código e acreditava que coisas que trocam mensagens por meio de substratos, diretamente ou modificando o DNA, executavam esse código. No geral, não era um modelo totalmente inútil, mas eu precisava saber quando não deveria ficar viciado nele.
  Para um biólogo com formação matemática, ver o DNA literalmente como um modelo de execução de uma máquina de Turing é claramente errado, mas para mim não era. No fim, é um problema que vem da estranheza do conhecimento básico.

• Decidibilidade, computabilidade, existência e até palavras como fruta têm significados diferentes em contextos acadêmicos e cotidianos. Quando a intuição do sentido cotidiano é levada para o contexto acadêmico, surgem essas “perguntas idiotas”.
  Certos números enormes que aparecem na Wikipedia “existem” e são “computáveis” no sentido acadêmico, mas seus dígitos não cabem dentro do nosso universo.

• Se você não ler com cuidado, a formulação confunde.
  Em “se Deus existe, defina f:{0,1}*→{0,1} como a função constante 1; se Deus não existe, como a função constante 0. f é computável?”, as alternativas não fazem parte da função.
  A função f não faz uma ramificação com base no valor de “Deus existe”; a ramificação está na metalinguagem. Não sabemos se f=0 ou f=1, mas, em qualquer caso, as duas funções possíveis são computáveis, portanto f também é computável.
  Indo além, mesmo que f de fato incluísse essa ramificação, e que o domínio da função fosse 0 (Deus não existe) e 1 (Deus existe), ela ainda seria uma função computável no sentido de que é possível calcular o resultado para cada valor do domínio.
  O ponto central da confusão está em empurrar para dentro de f, como condição de ramificação, uma variável livre cujo valor se considera desconhecido.

• Eu contestaria de bom grado o exemplo “suponha que n=3 se Deus existe, e n=5 se Deus não existe. n é primo?”.
  Aqui se está usando o terceiro excluído para afirmar que n é 3 ou 5, mas não há justificativa de que o terceiro excluído valha para a proposição “Deus existe”.

  • Na lógica clássica, o terceiro excluído é válido.
    Nesse caso, se vamos questionar se o terceiro excluído se justifica, também é preciso justificar por que apenas o terceiro excluído está sendo problematizado. Por que não abandonar também o princípio da explosão e trabalhar em paraconsistent logic? Kolmogorov também via problemas sérios nesse axioma e, no início, considerava-o incompatível com a lógica construtivista.
    Além disso, dependendo da formulação exata dessa proposição, talvez o terceiro excluído nem seja necessário.
  • Como referência, na versão do livro-texto está dito que se deve assumir que a pergunta é uma questão binária clara (Sipser, 2ª ed., p. 162). Perceber isso foi bastante perspicaz.
  • “n é primo?” também depende da vontade de Deus, se Deus existir.
    Deus pode não estar necessariamente preso às leis da física ou a necessidades lógicas fundamentais. Esse conceito de Deus vem de uma certa linhagem de raciocínio teológico, não é o caso geral.
    Se quiser, Deus também poderia fazer 6 ser ímpar. Poderia mudar toda a matemática, a consistência lógica e o universo inteiro, ou criar um mundo em que apenas 77 é par e todos os outros números são ímpares, e fazer todos os matemáticos considerarem esse arranjo totalmente consistente e sempre correto.
    Portanto, a resposta pode ser vista como dependendo, em certa medida, de crença religiosa.

• Ciência da computação teórica e teoria da complexidade parecem ocupar, para alunos de graduação em CS ou pessoas de setores adjacentes, uma posição parecida com a da física de partículas para o público geral.
  Assim como o público geral já ouviu falar em emaranhamento, nós já ouvimos falar em NP-difícil, e substituímos o acompanhamento direto do desenvolvimento matemático por metáforas populares ruins e fantasia.

  • Dito isso, não há motivo para achar que todo mundo deva usar a palavra “computável” apenas com uma definição extremamente rigorosa. A definição cotidiana, “algo que um computador consegue fazer”, também faz sentido.
    Talvez o autor, por causa de um longo treinamento, tenha escolhido sua própria definição muito estrita de computabilidade, escrito um texto inteiro sobre uma definição específica dessa palavra e depois acusado as pessoas do mundo, que usam a mesma palavra com outra definição, de fazerem perguntas idiotas.
    Isso acontece com muita frequência ao conversar com acadêmicos no trabalho ou com pessoas leigas. Estabelecer termos comuns é difícil, e é cansativo traçar uma linha com base nos próprios termos e depois mandar os outros acompanharem.