O equívoco zumbi da ciência da computação teórica

O equívoco zumbi da ciência da computação teórica

Introdução

• No livro didático "Introduction to the Theory of Computation", de Michael Sipser, há um exercício perfeito
• Exercício: "Se a função f:{0,1}*→{0,1} retorna 1 ou 0 dependendo da existência de Deus, então f é computável?"
• Resposta: "Sim, f é computável" (porque funções constantes são computáveis)

O conceito de computabilidade

• A computabilidade se aplica a funções ou sequências infinitas
• Não se aplica a perguntas individuais de sim/não nem a inteiros individuais
• A dificuldade de escrever um programa não tem relação com a computabilidade

O problema P versus NP

• O problema P versus NP é uma pergunta individual de sim/não
• NP-dificuldade se aplica a funções ou linguagens
• O problema P versus NP não pode ser incomputável nem NP-difícil

A função Busy Beaver

• A função Busy Beaver é incomputável
• Inteiros individuais como BB(6) são computáveis
• O que é incomputável é a função BB como um todo

O equívoco zumbi da ciência da computação teórica

• Aplicar por engano a inteiros individuais e problemas em aberto conceitos que se aplicam a sequências infinitas e funções
• Confundir a incomputabilidade do problema da parada com a incompletude de Gödel

Pergunta aos leitores

• O autor pergunta aos leitores como esse equívoco zumbi poderia ser evitado

Resumo do GN⁺

• Este texto trata de equívocos que surgem com frequência na ciência da computação teórica
• A computabilidade se aplica a funções ou sequências infinitas, e não a inteiros individuais ou perguntas de sim/não
• O problema P versus NP é uma pergunta individual e, portanto, não tem relação com o conceito de NP-dificuldade
• A função Busy Beaver é incomputável, mas valores individuais são computáveis
• Este texto ajuda a entender com clareza conceitos básicos da ciência da computação teórica

[GN⁺]

Comentários no Hacker News

• A questão de existir ou não um algoritmo para calcular a complexidade de Kolmogorov está relacionada ao infinito

  • Não existe algoritmo para calcular a complexidade de Kolmogorov de strings de comprimento arbitrário
  • Mas existe algoritmo para calcular a complexidade de Kolmogorov de strings com comprimento menor que n
  • Isso é possível criando uma enorme tabela de consulta para todas as strings possíveis
  • Problemas finitos sempre podem ser resolvidos por um programa, mas problemas infinitos não

• Opinião de que a matemática construtiva combina melhor com a intuição das pessoas

  • Ainda não há prova da existência de um programa para o problema P=NP
  • Mark Braverman provou que todo conjunto de Julia (quadrático) é computável, mas isso não é computável de forma uniforme
  • Na matemática construtiva, o plano complexo é dividido em várias regiões e se prova que, dentro de cada região, o conjunto de Julia é compacto

• Por que é difícil entender a indecidibilidade do problema da parada

  • Um dos programas, return true ou return false, sempre fornece a resposta correta
  • A decidibilidade só se torna indecidível quando é estendida para combinações infinitas de máquina/entrada

• Expressão de problemas que exigem lógica modal

  • A pergunta "f é computável?" é uma pergunta modalmente mal formulada
  • A pergunta "f poderia ser computável?" é mais precisa
  • Isso é semelhante a diretivas de compilador ou pragma

• A representação confusa da função f

  • A função f não ramifica com base no valor de "God exists"
  • Seja f 0 ou 1, ela é computável
  • A confusão surge ao empurrar variáveis livres para dentro da condição de ramificação

• Diferença de significado entre decidibilidade, computabilidade e existência

  • O significado difere entre o contexto acadêmico e o contexto cotidiano
  • Números grandes existem e são computáveis academicamente, mas, na prática, não cabem no universo

• O problema das perguntas relacionadas a "God exists"

  • Não está claro se "God exists" é verdadeiro ou falso
  • Esse é um problema que surge ao misturar linguagem natural e matemática

• Por que teoria da computação e teoria da complexidade são difíceis para alunos de graduação em Ciência da Computação

  • Termos como NP-hard acabam sendo substituídos por analogias populares e imaginação

• Reclamação sobre a forma de destaque de texto no blog

  • A cor de fundo do texto selecionado não muda, então não é intuitivo

• Proposta de substituir "God exists" por outra proposição matemática

  • É preciso definir "God exists" claramente como verdadeiro ou falso