Skip to content
TheChatArchiveThe Chat Archive
Claudeclaude-opus-4-20250514-thinking-16k· AnthropicHugging Face LMArena Human Preference 140K

Ahora quiero demostrar que el conjunto de todas las funciones N->N que NO son totales…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-flash-preview-04-17’s answer.
  1. User

    Ahora quiero demostrar que el conjunto de todas las funciones N->N que NO son totales computables, (\hat{TOT}) no es CE

  2. Claude Assistant

    Excelente pregunta. Para demostrar que \hat{TOT} (el complemento de TOT) no es computablemente enumerable, usaremos el hecho de que ya probamos que TOT no es CE.

    Demostración:

    Supongamos por contradicción que \hat{TOT} es computablemente enumerable.

    Si tanto TOT como \hat{TOT} fueran computablemente enumerables, entonces TOT sería decidible. Esto es porque:

    • Para decidir si un índice i corresponde a una función total computable, podríamos enumerar simultáneamente TOT y \hat{TOT}
    • El índice i eventualmente aparecería en exactamente una de las dos enumeraciones
    • Cuando aparezca, sabríamos con certeza si i∈TOT o i∈\hat{TOT}

    Pero si TOT fuera decidible, podríamos construir una enumeración computable de TOT de la siguiente manera:

    • Para n = 0, 1, 2, ...
    • Verificar si n∈TOT usando el algoritmo de decisión
    • Si n∈TOT, agregarlo a nuestra enumeración

    Esto nos daría una enumeración computable de TOT, lo cual contradice lo que acabamos de demostrar (que TOT no es CE).

    Por lo tanto, \hat{TOT} no puede ser computablemente enumerable.

    Nota adicional: Este resultado muestra que TOT es un conjunto que no es CE ni co-CE. En la jerarquía aritmética, TOT es un conjunto Π₂⁰-completo, lo cual está estrictamente por encima del nivel de los conjuntos CE (Σ₁⁰) y co-CE (Π₁⁰).

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.