Exercícios folha 6 2ª parte

26 Novembro 2021, 11:30 • André Souto

Resolução de exercícios sobre máquinas de Turing. 

Máquinas de Turing, continuação

26 Novembro 2021, 08:00 • Paulo Jorge Cunha Vaz Dias Urbano

Exercícios sobre Máquinas de Turing: uso de outras máquinas como sub-rotinas.

Exercícios folha 6 2ª parte

26 Novembro 2021, 08:00 • André Souto

Resolução de exercícios sobre máquinas de Turing. 

Incedibilidade. Aceitação e terminação em Máquinas de Turing

24 Novembro 2021, 09:30 • André Souto

Introdução aos problemas indecidíveis.

Definição e prova que  o problema de aceitação em máquinas de Turing é Turing-reconhecível.

Périplo para a demonstração que A_TM é indecidível. Argumento de diagonalização. Exemplos.

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.

Prova que A_TM é indecidível.

O problema da terminação e a sua indecidibilidade como introdução à noção de redutibilidade por mapeamento.

Noção de função computável.

Exemplos.

Definição formal de redução por mapeamento entre linguagens.

Resultados sobre linguagens redutíveis por mapeamento.

Exemplos.

Prova que o complementar de A_TM não é Turing reconhecível.

Prova que EQ_TM e o seu complementar não são Turing reconhecíveis.

Exercícios folha 6 2ª parte

24 Novembro 2021, 08:00 • André Souto

Resolução de exercícios sobre máquinas de Turing.