Rice–Shapiro theorem

From Wikipedia, the free encyclopedia
  (Redirected from Rice-Shapiro theorem)
Jump to: navigation, search

In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, and is named after Henry Gordon Rice and Norman Shapiro.[1]

Formal statement[edit]

Let A be a set of partial-recursive unary functions on the domain of natural numbers such that the set is recursively enumerable, where denotes the -th partial-recursive function in a Gödel numbering.

Then for any unary partial-recursive function , we have:

a finite function such that

In the given statement, a finite function is a function with a finite domain and means that for every it holds that is defined and equal to .

Perspective from Effective Topology[edit]

For any finite unary function on integers, let denote the 'frustum' of all partial-recursive functions that are defined, and agree with , on 's domain.

Equip the set of all partial-recursive functions with the topology generated by these frusta as base. Note that for every frustum , is recursively enumerable. More generally it holds for every set of partial-recursive functions:

is recursively enumerable iff is a recursively enumerable union of frusta.

Notes[edit]

  1. ^ Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. ISBN 0-262-68052-1. 

References[edit]

  • Cutland, Nigel (1980). Computability: an introduction to recursive function theory. Cambridge University Press. ; Theorem 7-2.16.
  • Rogers Jr., Hartley (1987). Theory of Recursive Functions and Effective Computability. MIT Press. p. 482. ISBN 0-262-68052-1. 
  • Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North Holland.