Sumários
Aula Teórica 5
1 outubro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia
Máquina de Turing com fita ilimitada à esquerda e à direita. Máquina de Turing com transições S. Máquina de Turing multifita. Exemplo: máquina de Turing com duas fitas que reconhece a linguagem das palavras do tipo \(a^nb^n\) com \(n\in\mathbb{N}_0\). Esboço da equivalência entre estas variantes e a noção de máquina de Turing definida anteriormente.
Aula Teórica 4
26 setembro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia
Especificação algébrica de Máquina de Turing. Exemplo. Classificador. Linguagem decidida por máquina de Turing. Linguagens semidecidíveis e decidíveis. Máquina de Turing como calculadora de funções. Exemplo: máquina de Turing que calcula a soma de naturais (representação unária dos naturais).
Especificação de máquinas de Turing
24 setembro 2013, 14:30 • João Rasga
Resolução dos exercicios: 1.1.a.i, 1.1.a.ii, 1.1.a.iii, 1.1.b, 1.2.a.i, 1.2.a.ii, 1.2.a.iii, 1.2.b, 2.1.c, 2.1.i e 2.4.b.
Aula Teórica 3
24 setembro 2013, 13:00 • Maria Paula Antunes Abrantes Gouveia
Exemplos de máquinas de Turing: (i) máquina cuja linguagem é o conjunto das palavras sobre \(\{0,1\}\) que terminam em 1, (ii) máquina cuja linguagem é o conjunto das palavras sobre \(\{a,b\}\) do tipo \(a^nb^n\), (iii) máquina cuja linguagem é o conjunto das palavras sobre \(\{a,b,c\}\) do tipo \(a^nb^mc^{n+m}\) (certificados da soma).
Aula Teórica 2
19 setembro 2013, 12:30 • Maria Paula Antunes Abrantes Gouveia
Computabilidade: motivação. Tese de Church-Turing. Alfabeto, palavra sobre alfabeto, palavra vazia, comprimento de palavra, linguagem sobre um alfabeto. Descrição informal de uma Máquina de Turing.