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

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

PrefixNamespace IRI
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpediahttp://dbpedia.org/resource/
Subject Item
dbpedia:Post_correspondence_problem
rdfs:comment
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often used in proofs of undecidability.
owl:differentFrom
dbpedia:Turing_degree dbpedia:PCP_theorem