Sumários

Variantes das máquinas de Turing

20 Novembro 2018, 09:30 • André Souto

Variantes das máquinas de Truing:

- Stay.
- Multi-fita.
- Fita duplamente infiinta.
- Não deterministica.
Prova que todas são equivalentes ao modelo de fita simples e portanto reconhecem/decidem as mesmas linguagens.
Os enumeradores.
Prova de equivalência entre enumeradores e máquinas de Turing de fita simples.
Operações com linguagens decidíveis e com linguagens reconhecíveis.

Estudar secção 3.2 do Sipser.

Resolução de exercícios da folha 7

19 Novembro 2018, 08:00 • André Souto

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

Resolução de exercícios da folha nº6

16 Novembro 2018, 11:30 • André Souto

Resolução de exercícios da folha nº6 sobre autómatos de pilha e gramáticas.

Exercício para avaliação contínua.

Resolução de exercícios da folha nº6

16 Novembro 2018, 08:00 • André Souto

Resolução de exercícios da folha nº6 sobre autómatos de pilha e gramáticas.

Exercício para avaliação contínua.

Continuação das Máquinas de Turing

14 Novembro 2018, 09:30 • André Souto

Revisão da definição formal de Máquina de Turing e de computação.

Máquinas de Turing que terminam para qualquer input (máquinas de decisão).  
Definição de linguagem Turing-reconhecível e Turing-decidível.
Exemplos de Máquinas de Turing para algumas linguagens e de configurações em máquinas de Turing.
Menção às variantes das máquinas de Turing: 
Variante Stay
Variante Multi-fita
Variante de fita infinita para ambos os lados
Variante não determinista.
Estudar secções 3.1 e 3.2 do Sipser.