We prove that the decision problem for finite mathematical state- ments, though recursive, is infeasible in seemingly any realistic model of computation. In particular, we construct of a set of finite mathematical statements which can only be feasibly solved by programs long enough to explicitly encode a decision for each statement. This result was published in Hungarian, in 1973, by Michael Makkai and appears here for the first time in English. In this paper we: 1) elucidate Makkai's proof as an adaptation of Gödel's first incompleteness proof, 2) strengthen his 1973 result and 3) reflect on this result from the perspectives of computational complexity and algorithmic information theory (Kolmogorov complexity). / Nous avons démontré que le problème quand à prendre des décisions concernant des énoncés mathématiques finis, bien que récursif, est infaisable accordé à n'importe quel modèle de calcul. Plus précisément, nous avons établi un ensemble de problèmes mathématiques ne pouvant être résolus que par des programmes assez long qui suggéreraient la décision finale implicitement, au fil des calculs. Ce fait a d'abord été publié en 1973 par un Hongrois du nom de Michael Makkai, et il sera expliqué en anglais pour la toute première fois ici. Dans ce travail, nous 1) éluciderons la démonstration faite par Makkai basé sur l'adaptation de la première démonstration du théorème incomplétude de Gödel, 2) appuierons les résultats trouvés en 1973 par Makkai et 3) tirerons des conclusions sur ses résultats en utilisant la théorie de la complexité et la théorie algorithmique de l'information, aussi appelée complexité de Kolmogorov.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.86989 |
| Date | January 2010 |
| Creators | Brown, Adam |
| Contributors | Patrick Hayden (Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (School of Computer Science) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0097 seconds