Reforço: Conjuntos e Diagonalização

Computabilidade e Complexidade

Autor

Márcio Nicolau

Data de Publicação

18 de agosto de 2025

Objetivos da Aula

  • Revisar e solidificar a diferença entre conjuntos enumeráveis e não-enumeráveis.
  • Aprofundar a compreensão da técnica de prova por diagonalização.
  • Conectar explicitamente a diagonalização de Cantor com a prova da indecidibilidade do Problema da Parada.
  • Reforçar por que esses conceitos são a base para os limites da computação.

Conteúdo

Revisitando o “Tamanho” dos Infinitos

No início do curso, estabelecemos uma ideia que parece paradoxal: nem todos os infinitos são do mesmo tamanho. Essa distinção é a pedra angular para entender por que existem problemas que os computadores não podem resolver. (Sipser, 2012)

NotaDefinições Essenciais (Revisão)
  • Conjunto Enumerável (ou Contável): Um conjunto é enumerável se seus elementos podem ser listados em uma sequência (ou seja, se existe uma correspondência um-para-um com os números naturais \(\mathbb{N}\)). Exemplos incluem os inteiros (\(\mathbb{Z}\)), os racionais (\(\mathbb{Q}\)) e, crucialmente, o conjunto de todos os programas de computador válidos.
  • Conjunto Não-Enumerável (ou Incontável): Um conjunto infinito que é “maior” que os números naturais. É impossível listar todos os seus elementos. O exemplo clássico é o conjunto dos números reais (\(\mathbb{R}\)). O exemplo mais importante para nós é o conjunto de todas as linguagens possíveis (ou seja, todos os problemas computacionais).

A conclusão fundamental para a ciência da computação é este descompasso:

Temos uma quantidade enumerável de possíveis soluções (programas), mas uma quantidade não-enumerável de possíveis problemas (linguagens).

Isso, por si só, já garante que devem existir problemas para os quais não há solução algorítmica. A ferramenta que nos permite provar isso rigorosamente é a diagonalização.

A Diagonalização: A Receita para Provar o Impossível

A prova por diagonalização é uma das técnicas mais elegantes e poderosas da matemática e da computação. É uma forma de prova por contradição com uma “receita” bem definida.

ImportanteA Receita da Diagonalização

Para provar que um conjunto S é não-enumerável:

  1. Assuma o Contraditório: “Suponha que S seja enumerável.”
  2. Liste os Elementos: Se é enumerável, podemos criar uma lista infinita \(e_1, e_2, e_3, \dots\) que contém todos os elementos de S.
  3. Construa a Grade: Organize essa lista em uma grade infinita, onde cada linha representa um elemento e cada coluna representa uma “característica” ou “parte” desse elemento.
  4. Construa o Antagonista: Crie um novo elemento, o “antagonista” \(D\), olhando para a diagonal da grade. A construção de \(D\) garante que sua \(i\)-ésima característica seja diferente da \(i\)-ésima característica do \(i\)-ésimo elemento da lista (\(e_i\)).
  5. Encontre a Contradição: O antagonista \(D\) é, por construção, um elemento válido do conjunto S. No entanto, ele não pode ser igual a nenhum elemento da lista, pois difere de \(e_i\) na \(i\)-ésima posição. Isso contradiz a suposição de que a lista continha todos os elementos.
  6. Conclua: A suposição inicial era falsa. O conjunto S é não-enumerável.

Diagrama: A Lógica da Diagonalização

graph TD
    A["Assuma que o conjunto S é enumerável"] --> B["Liste todos os elementos: L = (e₁, e₂, e₃, ...)"];
    B --> C["Construa a grade infinita"];
    C --> D["Construa o 'Antagonista' D<br/>modificando a diagonal da grade"];
    D --> E{"O Antagonista D está na lista L?"};
    E -- "Não, por construção!" --> F["<b>CONTRADIÇÃO!</b><br/>A lista não estava completa."];
    F --> G["A suposição inicial é falsa.<br/><b>S é Não-Enumerável</b>"];

    style F fill:#FFB6C1
Figura 1: A lógica universal da prova por diagonalização.

Aplicações: De Cantor a Turing

A genialidade de Turing foi perceber que essa mesma lógica poderia ser aplicada não apenas a números, mas a computações.

Aplicação de Cantor (Revisão)

  • Conjunto: Números reais \(\mathbb{R}\) entre 0 e 1.
  • Grade: Linhas são os números reais (\(r_i\)); colunas são seus dígitos decimais.
  • Diagonal: O \(i\)-ésimo dígito do \(i\)-ésimo número.
  • Antagonista: Um novo número real cujos dígitos são diferentes dos dígitos da diagonal.

Aplicação de Turing (A Prova do Problema da Parada)

  • Conjunto: Todas as Máquinas de Turing.
  • Grade: As linhas são todas as TMs (\(M_i\)). As colunas também são todas as TMs (\(M_j\)). A célula \((i, j)\) contém o resultado da execução de \(M_i\) na entrada \(\langle M_j \rangle\).
  • Diagonal: A célula \((i, i)\), que representa o que a máquina \(M_i\) faz quando recebe sua própria descrição como entrada.
  • Antagonista: A máquina \(D\) que, ao receber \(\langle M_i \rangle\), primeiro simula o comportamento da diagonal (\(M_i\) em \(\langle M_i \rangle\)) e depois faz o oposto.

Diagrama: O Paralelismo entre Cantor e Turing

graph LR
    subgraph "Prova de Cantor (Números Reais)"
        direction TB
        C1["<b>Lista de Reais (rᵢ)</b>"]
        C2["<b>Diagonal:</b><br/>O i-ésimo dígito de rᵢ"]
        C3["<b>Antagonista:</b><br/>Um novo real X que<br/>difere na diagonal."]
        C1 --> C2 --> C3
    end

    subgraph "Prova de Turing (Máquinas de Turing)"
        direction TB
        T1["<b>Lista de TMs (Mᵢ)</b>"]
        T2["<b>Diagonal:</b><br/>Comportamento de Mᵢ<br/>na entrada <Mᵢ>"]
        T3["<b>Antagonista:</b><br/>Uma nova TM 'D' que<br/>se comporta de forma oposta à diagonal."]
        T1 --> T2 --> T3
    end

    note["Mesma Estrutura Lógica"]
    C1 -.-> note -.-> T1

    style C1 fill:#e3f2fd
    style T1 fill:#e3f2fd
    style C3 fill:#ffcc99
    style T3 fill:#ffcc99
Figura 2: A mesma lógica de diagonalização usada em dois domínios diferentes.

Quando nos perguntamos “o que a máquina antagonista \(D\) faz com sua própria descrição \(\langle D \rangle\)?”, estamos forçando-a a olhar para sua própria posição na diagonal, onde, por construção, ela deve fazer o oposto de si mesma, levando à contradição.

Exercícios de Verificação

NotaAtividade Prática de Reforço

  1. Conceitual: Explique com suas próprias palavras por que o conjunto de todas as strings finitas compostas pelos caracteres ‘a’, ‘b’ e ‘c’ é enumerável. Qual seria uma estratégia para listá-las sem deixar nenhuma de fora?

  2. Aplicação da Técnica: Considere o conjunto F de todas as funções de \(\mathbb{N}\) para \(\mathbb{N}\) (ou seja, funções que recebem um número natural e retornam um número natural). Esboce um argumento de diagonalização para provar que este conjunto F é não-enumerável.

  3. Conexão Final: Na prova da indecidibilidade de \(A_{TM}\), a máquina antagonista \(D\) usa um suposto decisor \(H\) como sub-rotina. Qual é o papel da diagonal nessa prova específica? O que a consulta H(<M>, <M>) representa em termos da “grade” de Turing?

  1. Enumerabilidade das Strings: O conjunto é enumerável porque podemos listar as strings em uma ordem bem definida. A estratégia mais comum é a ordem canônica: listar primeiro por tamanho (comprimento 0, depois 1, depois 2, etc.) e, para strings de mesmo tamanho, usar a ordem alfabética (lexicográfica). Ex: ““,”a”, “b”, “c”, “aa”, “ab”, “ac”, “ba”, … . Toda string finita aparecerá eventualmente nesta lista.

  2. Prova para Funções de \(\mathbb{N}\) para \(\mathbb{N}\):

    • Assuma o contrário: Suponha que o conjunto F seja enumerável e possamos listar todas as funções: \(f_1, f_2, f_3, \dots\).
    • Construa a Grade: Imagine uma grade onde a linha \(i\) descreve a função \(f_i\) e a coluna \(j\) mostra o valor de \(f_i(j)\).
    • Construa o Antagonista: Defina uma nova função “antagonista” \(g: \mathbb{N} \to \mathbb{N}\) da seguinte forma: \(g(n) = f_n(n) + 1\).
    • Contradição: A função \(g\) é uma função válida de \(\mathbb{N}\) para \(\mathbb{N}\), então ela deve estar na nossa lista. Digamos que \(g = f_k\) para algum \(k\). Mas se tentarmos calcular \(g(k)\), teremos um paradoxo:
      • Pela definição de \(g\), \(g(k) = f_k(k) + 1\).
      • Como supomos que \(g = f_k\), então \(g(k) = f_k(k)\).
      • Isso leva a \(f_k(k) = f_k(k) + 1\), o que é impossível.
    • Conclusão: A suposição de que F é enumerável é falsa.

  3. Papel da Diagonal na Prova de \(A_{TM}\): A “grade” na prova de Turing tem TMs \(M_i\) nas linhas e descrições de TMs \(\langle M_j \rangle\) nas colunas. A diagonal representa a pergunta: “o que a máquina \(M_i\) faz quando recebe sua própria descrição \(\langle M_i \rangle\) como entrada?”. A consulta H(<M>, <M>) é exatamente a forma como a máquina antagonista \(D\) descobre o que está na diagonal para uma dada máquina \(M\), para que ela possa então fazer o oposto.

Referências Bibliográficas

SIPSER, Michael. Introdução à Teoria da Computação. 3. ed. São Paulo, Brasil: Cengage Learning, 2012.