Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/33698
Título: | Problemas indecidíveis | Autor: | Lobo, Diana de Castro | Orientador: | Kovacec, Alexander | Palavras-chave: | Algoritmo; Diofantina; Indecidibilidade; Mortalidade; Recursividade; Algorithm; Diophantine; Mortality; Recursivity; Unsolvability | Data: | 20-Set-2013 | Título da revista, periódico, livro ou evento: | Problemas indecidíveis | Local de edição ou do evento: | Coimbra | Resumo: | Este trabalho pretende explicar tanto quanto possível em linguagem
não excessivamente técnica o que se entende por um problema indecid
ível. De seguida, menciona o Problema da Correspondência de Post
(PCP) que foi provado como sendo indecidível por Emil Post em 1936.
Com base neste resultado, prova-se pormenorizadamente que a questão
de se um semigrupo (sob multiplicação) formado por um conjunto nito
de matrizes inteiras 3 x 3 contém a matriz nula é um problema indecid
ível. Na terceira e mais volumosa parte, a prova da indecibilidade do
famoso décimo problema de Hilbert é apresentada com base na simples
exposição de Martin Davis. This work aims to explain as far as possible what an unsolvable problem is, in a not exceedingly technical language. Next, the Post Correspondence Problem (PCP) is referred, a problem which was proved unsolvable by Emil Post in 1936. Based on this result, it is proved in detail that whether or not a nitely generated semigroup (under multiplication) of 3 x 3 integer matrices contains the null matrix is unsolvable. In the third and larger part, the proof of the unsolvability of Hilbert's famous tenth problem is presented, based on the simple exposition made by Martin Davis. |
Descrição: | Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra | URI: | https://hdl.handle.net/10316/33698 | Direitos: | openAccess |
Aparece nas coleções: | UC - Dissertações de Mestrado FCTUC Matemática - Teses de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Problemas indecidiveis_DianaLobo.pdf | 446.63 kB | Adobe PDF | Ver/Abrir |
Visualizações de página 50
457
Visto em 16/jul/2024
Downloads 20
1.308
Visto em 16/jul/2024
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.