Publication
Computability with polynomial differential equations
| dc.contributor.author | Graça, Daniel | |
| dc.date.accessioned | 2012-04-14T10:05:19Z | |
| dc.date.available | 2012-04-14T10:05:19Z | |
| dc.date.issued | 2007 | |
| dc.description | Tese dout., Matemática, Inst. Superior Técnico, Univ. Técnica de Lisboa, 2007 | por |
| dc.description.abstract | 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. | por |
| dc.identifier.other | AUT: DGR01772; | |
| dc.identifier.tid | 101159129 | |
| dc.identifier.uri | http://hdl.handle.net/10400.1/1027 | |
| dc.language.iso | eng | por |
| dc.relation | ConTComp: Continuous time computation and complexity | |
| dc.subject | Computabilidade | por |
| dc.subject | Intervalo maximal | por |
| dc.subject | Problemas de valor inicial | por |
| dc.subject | Equações diferenciais ordinárias | por |
| dc.subject | Análise computável | por |
| dc.subject | Computação analógica | por |
| dc.title | Computability with polynomial differential equations | por |
| dc.type | doctoral thesis | |
| dspace.entity.type | Publication | |
| oaire.awardTitle | ConTComp: Continuous time computation and complexity | |
| oaire.awardURI | info:eu-repo/grantAgreement/FCT/SFRH/SFRH%2FBD%2F17436%2F2004/PT | |
| oaire.awardURI | info:eu-repo/grantAgreement/FCT/POCI/POCTI%2FMAT%2F45978%2F2002/PT | |
| oaire.citation.conferencePlace | Universidade Técnica de Lisboa | por |
| oaire.fundingStream | SFRH | |
| oaire.fundingStream | POCI | |
| person.familyName | Graça | |
| person.givenName | Daniel | |
| person.identifier.ciencia-id | 2D11-56DE-3F11 | |
| person.identifier.orcid | 0000-0002-0330-833X | |
| person.identifier.rid | D-2335-2011 | |
| person.identifier.scopus-author-id | 8882791800 | |
| project.funder.identifier | http://doi.org/10.13039/501100001871 | |
| project.funder.identifier | http://doi.org/10.13039/501100001871 | |
| project.funder.name | Fundação para a Ciência e a Tecnologia | |
| project.funder.name | Fundação para a Ciência e a Tecnologia | |
| rcaap.rights | openAccess | por |
| rcaap.type | doctoralThesis | por |
| relation.isAuthorOfPublication | ba0c1461-5d2d-4f06-b648-df4a1a505bdf | |
| relation.isAuthorOfPublication.latestForDiscovery | ba0c1461-5d2d-4f06-b648-df4a1a505bdf | |
| relation.isProjectOfPublication | 5cbba14a-0c72-415f-96b3-df9de4a0c542 | |
| relation.isProjectOfPublication | 98f724cf-a2ae-4a98-8827-9ba4c02c5abb | |
| relation.isProjectOfPublication.latestForDiscovery | 98f724cf-a2ae-4a98-8827-9ba4c02c5abb |