Máquinas de Turing

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

Exercícios sobre Máquinas de Turing

Operações com linguagens Turing decidíveis e Turing reconhecíveis.

17 Novembro 2021, 09:30 • André Souto

Operações com linguagens decidívies e Turing reconhecíveis.

A tese de Church Turing.

Noção de algoritmo e descrição de alto nível de uma máquina de Turing.

Noção de codificação para inputs de máquinas de Turing. 

Exemplos de codificação de problemas em grafos e de problemas sobre máquinas de Turing. Noção de máquina de Turing universal.

Estudar a secção 3.2 e 3.1 do Sipser.

Exercícios folha 6

17 Novembro 2021, 08:00 • André Souto

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

Exercícios folha 6

16 Novembro 2021, 10:30 • André Souto

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

Variantes das MT

16 Novembro 2021, 09:30 • André Souto

Exemplo de máquina de Turing.

Variantes das máquinas de Turing: versão Stay, multifita, fita infinta para ambos os lados e não determinista.

Equivalência entre todas as variantes por equivalência à máquina de Turing standard. 

Estudar secção 3.1 e 3.2 do Sipser.