This HTML5 document contains 19 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dct	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
n5	http://en.wikipedia.org/wiki/
dbp	http://dbpedia.org/property/
dbc	http://dbpedia.org/resource/Category:
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
dbr	http://dbpedia.org/resource/

Statements

Subject Item

dbr:Rice's_theorem

rdfs:label

Rice's theorem

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.

owl:sameAs

yago-res:Rice's_theorem freebase:m.06g1h

dbp:wikiPageUsesTemplate

dbt:Short_description dbt:Var dbt:Math dbt:MathWorld dbt:Citation

dct:subject

dbc:Theorems_in_theory_of_computation dbc:Articles_containing_proofs dbc:Undecidable_problems dbc:Theorems_in_the_foundations_of_mathematics

prov:wasDerivedFrom

n5:Rice's_theorem?oldid=1065033143&ns=0

dbo:wikiPageID

25852

dbo:wikiPageLength

20500

dbo:wikiPageRevisionID

1065033143

dbo: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.

foaf:isPrimaryTopicOf

n5:Rice's_theorem