About: Rice's theorem

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Rice's theorem Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : el.dbpedia.org associated with source document(s)

In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function.

Attributes	Values
rdfs:label	Rice's theorem (en)
rdfs:comment	In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function. (en)
sameAs	Rice's theorem Rice's theorem
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Math dbt:MathWorld dbt:Short_description dbt:Var
Subject	Articles containing proofs Undecidable problems Theorems in the foundations of mathematics Theorems in theory of computation
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Rice's_theorem?oldid=1065033143&ns=0
Wikipage page ID	25852 (xsd:integer)
page length (characters) of wiki page	20500 (xsd:nonNegativeInteger)
Wikipage revision ID	1065033143 (xsd:integer)
has abstract	In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). A property is non-trivial if it is neither true for every partial computable function, nor false for every partial computable function. Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property. Here, a property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm. The theorem is named after Henry Gordon Rice, who proved it in his doctoral dissertation of 1951 at Syracuse University. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Rice's_theorem
is Wikipage redirect of	Rice's Theorem Rices theorem Rice-Myhill-Shapiro Theorem Rice-Myhill-Shapiro theorem Rice s Theorem Rice theorem Rices Theorem Rice–Myhill–Shapiro theorem
is Link from a Wikipage to another Wikipage of	List of theorems List of undecidable problems Abstract interpretation Abstraction (computer science) Bootstrapping (compilers) Cantor's diagonal argument Generic-case complexity Myhill List of mathematical logic topics List of mathematical proofs Combinatory logic Complete numbering Computability Computability theory Henry Gordon Rice Definite assignment analysis Full employment theorem Index set (computability) Expressive power (computer science) Halting problem John Myhill
is known for of	John Myhill

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (82 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software