Decidibilidade.
22 Novembro 2022, 09:30 • Ana Respicio
A tese de Church Turing: Terminologia para descrever Máquinas de Turing. Codificação de objetos. Codificação de um grafo. O problema de decidir se um grafo direcionado é conexo é decidível.
Sipser, Cap 3, secção 3.
Decidibilidade: Introdução. Linguagens decidíveis. Problemas decidíveis relativos a Linguagens Regulares. O problema de testar se um Autómato Finito Determinista aceita uma dada palavra é decidível.
Sipser, Cap 4, secção 1.