2.1.6 AL/Teoría y Computabilidad Avanzada de Autómatas

Tópicos:
Electivo

Objetivos de Aprendizaje:
Elective:

  1. Determina la ubicación de un lenguaje en la jerarquía de Chomsky (regular, libre de contexto, enumerable recursivamente) [Evaluar]
  2. Convierte entre notaciones igualmente poderosas para un lenguaje, incluyendo entre estas AFDs, AFNDs, expresiones regulares, y entre AP y GLCs [Usar]
  3. Explica la tesis de Church-Turing y su importancia [Familiarizarse]
  4. Explica el teorema de Rice y su importancia [Familiarizarse]
  5. Da ejemplos de funciones no computables [Familiarizarse]
  6. Demuestra que un problema es no computable al reducir un problema clásico no computable en base a él [Usar]

Generado por Ernesto Cuadros-Vargas , Sociedad Peruana de Computación-Peru, Universidad de Ingeniería y Tecnología, Lima-Perú
basado en el modelo de la Computing Curricula de IEEE-CS/ACM