Sumários
Aula Teórica 17
20 novembro 2012, 08:30 • Maria Paula Antunes Abrantes Gouveia
Codificação de máquinas de Turing em palavras sobre \(\{0,1\}\). Proposição: O conjunto \(\cal{M}\) das máqunas de Turing é equipotente a \(\mathbb{N}_0\). Proposição: Existem linguagens que não são reconhecidas por nenhuma máquina de Turing. Proposição: Existem funções de \(\{0,1\}^*\) para \(\{0,1\}^*\) que não são computáveis. Máquinas de Turing multi-fita. Exemplo: máquina de 2 fitas que decide a linguagem \(a^nb^n\).
Exercícios sobre máquinas de Turing deterministas.
20 novembro 2012, 08:00 • João Rasga
Resolução dos exercícios: 1.4a, 1.4b, 2.1i, 2.2a, 2.10 e 2.11a.
Aula Prática 9
16 novembro 2012, 12:00 • Maria Paula Antunes Abrantes Gouveia
Exercícios 2.1 a) b), 2.2 a) e) g) e 2.3 a) e) da lista de exercícios para a aula prática 8.
Exercícios sobre equipotência e não equipotência de conjuntos.
15 novembro 2012, 12:00 • João Rasga
Resolucação dos exercícios: 2.2a, 2.3a, 2.2e, 2.2f e 2.2g,
Aula Teórica 16
15 novembro 2012, 12:00 • Maria Paula Antunes Abrantes Gouveia
Máquina de Turing que decide a linguagem \(a^nb^nc^n\). Máquina de Turing que calcula a função \(f:\{0,2\}^*\to \{0,1,2\}^*\) dada por \(f(w)=w1w\). Operações sobre linguagens decidíveis e semi-decidíveis: (i) se \(L_1,L_2\subseteq \Sigma^*\) são decidíveis então \(L_1\cup L_2\), \(L_1\cap L_2\) e \(\Sigma^*\backslash L_2\) são decidíveis; (ii) se \(L_1,L_2\subseteq \Sigma^*\) são semi-decidíveis e se \(L_3\subseteq \Sigma^*\) é decidível então \(L_1\cap L_2\), \(L_1\cup L_3\) e \(L_1\backslash L_3\) são semi-decidíveis.