Portal de Periódicos da CAPES

Recursively Enumerable Sets and Degrees

1987; Cambridge University Press; Linguagem: Inglês

10.1007/978-3-662-02460-7

0172-6641

Robert I. Soare,

Computability, Logic, AI Algorithms

BY ROBERT I. SOARE 1 logic, and recursively enumerable sets form the soul of recursion theory.Although some might challenge these claims, it is clear that recursively enumerable sets have played an important role in logic beginning with the first undecidability results of Gödel [Göl], Church [Ch] and Rosser [Rs].Furthermore, the notion of a recursively enumerable set rather than that of a recursive (i.e, computable) function has proved to be the fundamental concept in attempts to generalize classical recursion theory to more general settings, such as admissible ordinals [Sh4], [Le6], or higher types [Sa9].A subset A of <o (the set of nonnegative integers) is recursive (also called decidable or computable) if there is an algorithm for determining whether a