Rice-Shapiro theorem

Rice-Shapiro theorem

In computability theory, the Rice-Shapiro theorem is a generalization of Rice's theorem, and is named after Henry Gordon Rice and Stewart Shapiro cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | year=1987] .

Informal statement

The statement can be expressed informally as follows: given that a computable function (viewed as a black-box) is an infinite object, and we cannot hope to develop a general algorithm studying a property of function on infinite input-output pairs; there is in general no truly better way than to apply the function on some inputs and hope to get their outputs.

Formal statement

Let A be a set of computable unary functions on the domain of natural numbers such that the set { n mid varphi_n in A } is recursively enumerable, where varphi_n denotes the n-th computable function in a Gödel numbering.

Then for any unary computable function f, we have:

:f in A Leftrightarrow existsmbox{ a finite function } heta subseteq fmbox{ such that } heta in A.

In the given statement, heta subseteq f means that heta is an approximation of f, and finite function refers to a function defined on a finite set of input values.

Notes

References

*cite book | title=Computability: an introduction to recursive function theory| author=Cutland, Nigel | publisher=Cambridge University Press | year=1980 ; Theorem 7-2.16.
* cite book | title=Theory of Recursive Functions and Effective Computability | author=Rogers Jr., Hartley | publisher=MIT Press|isbn=0-262-68052-1 | pages=482 | year=1987


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Rice's theorem — In computer science, Rice s theorem named after Henry Gordon Rice (also known as The Rice Myhill Shapiro theorem after Rice and John Myhill) states that, for any non trivial property of partial functions, there exists at least one algorithm for… …   Wikipedia

  • Norman Shapiro — Norman Z. Shapiro (born 1932) is an American mathematician, who is the co author of the Rice–Shapiro theorem. Shapiro spent the summer of 1954 at Bell Laboratories in Murray Hill, New Jersey where, in collaboration with Karel de Leeuw, Ed Moore,… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • John Myhill — John R. Myhill (Senior) was a mathematician. He received his Ph.D. from Harvard University under Willard Van Orman Quine in 1949. He was professor at SUNY Buffalo from 1966 until his death in 1987. He also taught at several other universities.In… …   Wikipedia

  • List of undecidable problems — In computability theory, an undecidable problem is a problem whose language is not a recursive set. More informally, such problems cannot be solved in general by computers; see decidability. This is a list of undecidable problems. Note that there …   Wikipedia

  • Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia

  • List of statistics topics — Please add any Wikipedia articles related to statistics that are not already on this list.The Related changes link in the margin of this page (below search) leads to a list of the most recent changes to the articles listed below. To see the most… …   Wikipedia

  • Shing-Tung Yau — at Harvard Law School dining hall Born …   Wikipedia

  • Peter Lax — Peter David Lax Peter Lax in Tokyo, 1969 Born 1 May 1926 ( …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”