A note on recursively enumerable classes of partial recursive functions

Jan van Leeuwen

A note on recursively enumerable classes of partial recursive functions

Jan van Leeuwen

Research output: Book/Report › Report › Academic

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 language	English
Place of Publication	Utrecht
Publisher	UU BETA ICS Departement Informatica
Number of pages	11
Publication status	Published - Jan 2015

Publication series

Name	Technical Report Series
Publisher	UU 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

Access to Document

2015-001Final published version, 180 KB

Cite this

@book{b32541b4874c4081959b99726e94f5cd,

title = "A note on recursively enumerable classes of partial recursive functions",

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.",

keywords = "Recursively enumerable classes, Rice-Shapiro theorem, recursive witness arrays, recursive permutations",

author = "\{van Leeuwen\}, Jan",

year = "2015",

month = jan,

language = "English",

series = "Technical Report Series",

publisher = "UU BETA ICS Departement Informatica",

number = "UU-CS-2015-001",

}

TY - BOOK

T1 - A note on recursively enumerable classes of partial recursive functions

AU - van Leeuwen, Jan

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - Recursively enumerable classes

KW - Rice-Shapiro theorem

KW - recursive witness arrays

KW - recursive permutations

M3 - Report

T3 - Technical Report Series

BT - A note on recursively enumerable classes of partial recursive functions

PB - UU BETA ICS Departement Informatica

CY - Utrecht

ER -

A note on recursively enumerable classes of partial recursive functions

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this