Aula Teórica 13

9 novembro 2010, 08:30 • Maria Paula Antunes Abrantes Gouveia

Exemplo: máquina de Turing que decide a linguagem w2w  onde w é uma palavra binária (exercício 2.4 a) da lista de exercícios para a aula prática 9). Configuração de máquina de Tiring, configurações inicial, de aceitação, de rejeição  e de paragem. Classificador. Linguagem reconhecida por máquina de Turing e linguagem decidida por máquina de Turing. Linguagem decidível. Máquina de Turing como calculadora de funções. Exemplo: máquina de Turing que calcula a função que a cada palavra binária faz corresponder a sua negação (exercício 2.9 a) da lista de exercícios para a aula prática 9 ).