2.2.10 AL/Computabilidad y Decidibilidad

Temas:
Core

• Decidabilidad, (in)computabilidad y parada
• La tesis de Church-Turing
• Corrección algorítmica:
  1. Invariantes (por ejemplo, en iteración, recursión, búsqueda en árbol)
• Decidabilidad:
  1. Aritmetización y diagonalización
• Reducibilidad y reducciones
• Complejidad de tiempo basada en Máquina de Turing
• Complejidad de espacio (por ejemplo, Pspace, Teorema de Savitch)

Non Core

• Computación cuántica:
  1. Postulados de la mecánica cuántica:
     1. Espacio de estados
     2. Evolución del estado
     3. Composición de estados
     4. Medición del estado
  2. Representaciones de vector columna de qubits
  3. Representaciones matriciales de operaciones cuánticas
  4. Compuertas cuánticas simples (por ejemplo, XNOT, CNOT)

Aprendizaje esperado (Learning Outcomes):
Core:

1. Explicar una Máquina de Turing universal y su operación [Explicar]
2. Presentar a una audiencia de compañeros de trabajo y gerentes la imposibilidad de proporcionarles un programa que verifique todos los otros programas, incluyendo algunos aparentemente simples, en busca de bucles infinitos incluyendo una explicación del problema de la parada, por qué no tiene solución algorítmica y su importancia para la computación algorítmica del mundo real [Explicar]
3. Explicar ejemplos de problemas clásicos incomputables [Explicar]
4. Explicar la Tesis de Church-Turing y su importancia para la computación algorítmica [Explicar]
5. Explicar cómo los invariantes (de bucle) pueden usarse para demostrar la corrección de un algoritmo [Explicar]
6. Aplicar aritmetización y diagonalización para demostrar que el Problema de la Parada para Máquinas de Turing es Indecidible [Aplicar]
7. Dado un lenguaje indecidible conocido, aplicar una reducción por mapeo o historia computacional para demostrar que otro lenguaje es indecidible [Aplicar]
8. Explicar el teorema de Rice y su importancia [Explicar]
9. Explicar un ejemplo de demostración de un problema que es incomputable reduciendo un problema incomputable clásico conocido a él [Explicar]
10. Explicar las funciones Recursivas Primitivas y Generales (cero, sucesor, selección, recursión primitiva, composición y Mu), su importancia e implementaciones en Máquina de Turing [Explicar]
11. Explicar cómo se realiza la computación en el Cálculo Lambda (por ejemplo, conversión alfa y reducción beta) [Explicar]

NonCore:

1. Para un sistema cuántico dar ejemplos que expliquen los siguientes postulados:
   1. Espacio de Estados - estado del sistema representado como un vector unitario en espacio de Hilbert
   2. Evolución del Estado - el uso de operadores unitarios para evolucionar el estado del sistema
   3. Composición de Estados - el uso de producto tensorial para componer estados del sistema
   4. Medición del Estado - la salida probabilística de medir un estado del sistema.
   [Explicar]
2. Explicar la operación de una compuerta cuántica XNOT o CNOT sobre un bit cuántico representado como una matriz y vector columna, respectivamente [Explicar]