Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/1027
Título: Computability with polynomial differential equations
Autor: Graça, Daniel
Palavras-chave: Computabilidade
Intervalo maximal
Problemas de valor inicial
Equações diferenciais ordinárias
Análise computável
Computação analógica
Data de Defesa: 2007
Resumo: Nesta dissertação iremos analisar um modelo de computação analógica, baseado em equações diferenciais polinomiais. Começa-se por estudar algumas propriedades das equações diferenciais polinomiais, em particular a sua equivalência a outro modelo baseado em circuitos analógicos (GPAC), introduzido por C. Shannon em 1941, e que é uma idealização de um dispositivo físico, o Analisador Diferencial. Seguidamente, estuda-se o poder computacional do modelo. Mais concretamente, mostra-se que ele pode simular máquinas de Turing, de uma forma robusta a erros, pelo que este modelo é capaz de efectuar computações de Tipo-1. Esta simulação é feita em tempo contínuo. Mais, mostramos que utilizando um enquadramento apropriado, o modelo é equivalente à Análise Computável, isto é, à computação de Tipo-2. Finalmente, estudam-se algumas limitações computacionais referentes aos problemas de valor inicial (PVIs) definidos por equações diferenciais ordinárias. Em particular: (i) mostra-se que mesmo que o PVI seja definido por uma função analítica e que a mesma, assim como as condições iniciais, sejam computáveis, o respectivo intervalo maximal de existência da solução não é necessariamente computável; (ii) estabelecem-se limites para o grau de não-computabilidade, mostrando-se que o intervalo maximal é, em condições muito gerais, recursivamente enumerável; (iii) mostra-se que o problema de decidir se o intervalo maximal é ou não limitado é indecídivel, mesmo que se considerem apenas PVIs polinomiais.
Descrição: Tese dout., Matemática, Inst. Superior Técnico, Univ. Técnica de Lisboa, 2007
URI: http://hdl.handle.net/10400.1/1027
Aparece nas colecções:FCT1-Teses

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Daniel-Graca-PhDthesis.pdf1,02 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.