Skip to content
TheChatArchiveThe Chat Archive
o3-mini· OpenAIHugging Face LMArena Human Preference 140K

Hola! Necesito ayuda para resolver un problema de teoria de computabilidad. El problema…

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-3-7-sonnet-20250219’s answer.
  1. User

    Hola! Necesito ayuda para resolver un problema de teoria de computabilidad.

    El problema es el siguiente. Demostrar que el conjunto de todas las funciones computables de N->N llamado TOT, no es computablemente enumerable

  2. Assistant

    Queremos demostrar que el conjunto [ \text{TOT} = { e \in \mathbb{N} \mid \varphi_e : \mathbb{N} \to \mathbb{N} \text{ es total}} ] no es computablemente enumerable (c.e.). A continuación, se presenta una demostración por diagonalización.


    Suposición inicial

    Supongamos, para llegar a una contradicción, que TOT es computablemente enumerable. Esto implica que existe un algoritmo o proceso efectivo que puede listar (enumerar) todos los índices de máquinas de Turing (o programas) que corresponden a funciones totales. Es decir, podemos enumerarlas como:

    [ e_0, e_1, e_2, \dots ]

    donde para cada ( i ), la función ( \varphi_{e_i} ) definida por el programa con índice ( e_i ) es total (está definida para todo ( n \in \mathbb{N} )).


    Construcción del contraejemplo por diagonalización

    Usando esta enumeración, definimos una nueva función ( f: \mathbb{N} \to \mathbb{N} ) de la siguiente manera:

    [ f(n) = \varphi_{e_n}(n) + 1. ]

    Analicemos las propiedades de ( f ):

    1. ( f ) es total:
      Para cada ( n \in \mathbb{N} ), el dato ( \varphi_{e_n}(n) ) está definido porque, por suposicián, ( \varphi_{e_n} ) es total. Sumándole 1, también tenemos que ( f(n) ) está definido para todo ( n ).

    2. ( f ) es computable:
      Dado que la enumeración ( e_0, e_1, e_2, \dots ) es efectiva y se puede simular ( \varphi_{e_n}(n) ) (puesto que ( \varphi_{e_n} ) es total y computable), la función ( f ) es computable.

    Ahora, al ser ( f ) una función total computable, debe aparecer en la lista enumerada. Es decir, por la exhaustividad de la enumeración, existe un ( k \in \mathbb{N} ) tal que: [ \varphi_{e_k} = f. ]

    Examinemos lo que sucede evaluando ambas funciones en el argumento ( k ):

    • Por la definición de ( f ): [ f(k) = \varphi_{e_k}(k) + 1. ]
    • Pero, dado que ( \varphi_{e_k} = f ), también tenemos: [ f(k) = \varphi_{e_k}(k). ]

    Juntando ambas ecuaciones obtenemos: [ \varphi_{e_k}(k) = \varphi_{e_k}(k) + 1, ] lo cual es una contradicción (pues no existe ningún número ( x ) que cumpla ( x = x+1 )).


    Conclusión

    La contradicción obtenida surge de la suposición inicial de que TOT era computablemente enumerable. Por lo tanto, debemos rechazar esa suposición y concluir que:

    [ \boxed{\text{TOT no es computablemente enumerable.}} ]

    Esta demostración es un clásico argumento de diagonalización que, de manera similar a la construcción de la función diagonal (tipo Cantor), muestra que siempre se puede construir una función total computable que no figura en cualquier posible enumeración de las funciones totales computables.

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