A note on recursively enumerable classes of partial recursive functions

    Research output: Book/ReportReportAcademic

    Abstract

    We prove that every recursively enumerable class of partial recursive functions with infinite domains must have a recursive witness array. The result gives a powerful method for proving properties of recursively enumerable classes. We
    show for example that no finitely generated group of recursive permutations can contain all recursive involutions, and neither can it contain all cycle-free recursive permutations.
    Original languageEnglish
    Place of PublicationUtrecht
    PublisherUU BETA ICS Departement Informatica
    Number of pages11
    Publication statusPublished - Jan 2015

    Publication series

    NameTechnical Report Series
    PublisherUU Beta ICS Departement Informatica
    No.UU-CS-2015-001
    ISSN (Print)0924-3275

    Keywords

    • Recursively enumerable classes
    • Rice-Shapiro theorem
    • recursive witness arrays
    • recursive permutations

    Fingerprint

    Dive into the research topics of 'A note on recursively enumerable classes of partial recursive functions'. Together they form a unique fingerprint.

    Cite this