Indecidibilidade

24 Novembro 2020, 09:30 • André Souto

Decidibilidade de linguagens baseadas em linguagens livres de contexto.

Introdução aos problemas indecidíveis.

O problema de aceitação em máquinas de Turing.

Prova que é Turing-reconhecível.

Periplo para a demonstração que é indecidível.

Argumentos de diagonalização.

Noção de conjunto enumerável.

Exemplos de conjuntos enumeráveis: N, Z e Q, conjunto das máquinas de Turing e de todas as strings.

Prova que R e que o conjunto das sequências infinitas e consequentemente o conjunto de todas as linguagnes não é numerável.