Supõe-se que a duração do semestre é de 20 semanas. Podem, assim, contar-se 15 semanas efectivas de aulas. Supõe-se uma carga horária de 4 horas teórico‑práticas, que dividimos em componente teórica (condução do docente) e componente prática (condução dos alunos).
A distribuição destas 15 semanas pelos vectores da disciplina é como segue. Serão dedicadas 5 semanas à componente operacional, 5 semanas à componente axiomática e 5 semanas à componente denotacional.
Os tópicos programáticos são:
I. Algoritmos ou procedimentos efectivos; A máquina de registos: comandos e programas; Máquinas de Turing: constituição e modo de operacção; Máquina de Johnstone: estados, comandos e programas; Convergência e divergência; Funções computáveis pela máquina URM, pelas máquinas de Turing e pela máquina de Johnstone; Critérios de Computabilidade URM, Turing e Johnstone; Predicados decidíveis; Outros domínios para a computabilidade; Postulado de Chuch.
II. Axiomatização da computabilidade; Primitivas; Composição sequêncial; Métodos para construir novas funções a partir de funções já definidas: substituição, recorrência e minimização.
III. Codificação de programas; As funções p, z e t; Codificação de funções computáveis; O teorema s-m-n; Funções universais e programas universais; Problemas de indecidibilidade na computabilidade.
Supõe-se que a duração do semestre é de 20 semanas. Podem, assim, contar-se 15 semanas efectivas de aulas. Supõe-se uma carga horária de 4 horas teórico‑práticas, que dividimos em componente teórica (condução do docente) e componente prática (condução dos alunos).
A distribuição destas 15 semanas pelos vectores da disciplina é como segue. Serão dedicadas 5 semanas à componente operacional, 5 semanas à componente axiomática e 5 semanas à componente denotacional.
Os tópicos programáticos são:
I. Algoritmos ou procedimentos efectivos; A máquina de registos: comandos e programas; Máquinas de Turing: constituição e modo de operacção; Máquina de Johnstone: estados, comandos e programas; Convergência e divergência; Funções computáveis pela máquina URM, pelas máquinas de Turing e pela máquina de Johnstone; Critérios de Computabilidade URM, Turing e Johnstone; Predicados decidíveis; Outros domínios para a computabilidade; Postulado de Chuch.
II. Axiomatização da computabilidade; Primitivas; Composição sequêncial; Métodos para construir novas funções a partir de funções já definidas: substituição, recorrência e minimização.
III. Codificação de programas; As funções p, z e t; Codificação de funções computáveis; O teorema s-m-n; Funções universais e programas universais; Problemas de indecidibilidade na computabilidade.