In this thesis possible characterizations of the category of primitive recursive functions and the category of recursive functions are studied. Closed cartesian categories, closed under the Peano-Lawvere axiom, whlch are called pre-recursive, are considered first. Representable functlons in such a category are introduced. Every primitive recursive function is representable in a pre-recursive category. In ⍕, the free pre-recursive category generated by the empty category Φ, every morphism T → N is a natural number, and every morphism N[n] → N[m] , n ∊ N, m ∊ N, represents a recursive function. Furthermore, a morphism representing a function which is not primitive recursive is found. A recursive function whlch is not representable in ⍕ is constructed. Following the above, structures of primitive recursive category and structures of recursive category are proposed, each structure generating a category whose class of representable functions is respectively the class of primitive recursive functions and the class of recursive functlons. / Pouvons-nous caractériser la catégorie des fonctions primitives récursives, la catégorie des fonctions récursives? Considérons les catégories cartésiennes fermées, fermées sous l'axiome de Peano-Lawvere, que nous appellerons pré-récursives et précisons ce qu'est une fonction représentable dans une telle catégorie. Toute fonction primitive récursive est représentable dans une catégorie pré-récursive. Dans, la catégorie pré-récursive libre engendrée par la catégorie vide, tout morphisme T->N représente un nombre naturel et tout morphisme N[n] -> N[m], n N, m N, représente une fonction récursive. De plus, on peut trouver un morphisme qui représente une fonction qui n'est pas primitive récursive et construire une fonction récursive non représentable dans $. A la suite de ces résultats, nous présentons des structures de catégorie primitive récursive et de catégorie récursive, chaque structure engendrantune catégorie dont la classe des fonctions représentables est respectivement la class des fonctions primitives récursives et celle des fonctions récursives. fr
Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.66635 |
Date | January 1977 |
Creators | Thibault, Marie-France |
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 | Doctor of Philosophy (Department of Mathematics) |
Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
Page generated in 0.0015 seconds