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

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

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n6http://dbpedia.org/resource/Magic:
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_undecidable_problems
rdf:type
dbo:Disease
rdfs:label
List of undecidable problems
rdfs:comment
In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. More formally, an undecidable problem is a problem whose language is not a recursive set; see the article Decidable language. There are uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of Turing recognizable languages: i.e., such undecidable languages may be recursively enumerable.
dbp:wikiPageUsesTemplate
dbt:Citation dbt:Short_description dbt:Reflist dbt:Cite_journal dbt:Cite_book
dct:subject
dbc:Computability_theory dbc:Lists_of_problems dbc:Mathematics-related_lists dbc:Theory_of_computation dbc:Undecidable_problems
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
n10:List_of_undecidable_problems?oldid=1036516846&ns=0
dbo:wikiPageID
1188090
dbo:wikiPageLength
12228
dbo:wikiPageRevisionID
1036516846
dbo:wikiPageWikiLink
dbr:Integer_matrix dbr:Zero_matrix dbr:Recursive_language dbr:Ordinary_differential_equation dbr:Halting_problem n6:_The_Gathering dbc:Mathematics-related_lists dbr:Lambda_calculus dbr:Type_inference dbr:Type_system dbr:Risch_algorithm dbr:Richardson's_theorem dbr:Simply_connected_space dbr:Hilbert's_tenth_problem dbr:Uncountable_set dbr:Subset dbr:Lists_of_problems dbr:Computable_set dbr:Busy_beaver dbr:Fare dbr:List_of_statements_independent_of_ZFC dbr:Fundamental_group dbr:Group_isomorphism_problem dbr:Register_machine dbc:Undecidable_problems dbr:Homeomorphism dbc:Lists_of_problems dbr:Mortality_(computability_theory) dbr:Context-free_grammar dbr:Tag_system dbr:Simplicial_complex dbr:Wang_tile dbr:Trakhtenbrot's_theorem dbr:Entscheidungsproblem dbr:Partially_observable_Markov_decision_process dbr:Logic_of_graphs dbr:Turing_machine dbr:5-manifold dbr:Horn_clause dbc:Computability_theory dbc:Theory_of_computation dbr:Vector_(mathematics_and_physics) dbr:Conjugacy_problem dbr:Air_travel dbr:Kolmogorov_complexity dbr:Diophantine_set dbr:Lists_of_unsolved_problems dbr:Undecidable_problem dbr:Pushdown_automaton dbr:Conway's_Game_of_Life dbr:Word_problem_(mathematics) dbr:Polynomial dbr:Spectral_gap_(physics) dbr:Semigroup dbr:Reduction_(complexity) dbr:Post_correspondence_problem dbr:Computational_problem dbr:Alan_Turing dbr:Rule_110 dbr:Rice's_theorem dbr:System_F dbr:Word_problem_for_groups dbr:MathOverflow dbr:Manifold dbr:Computability_theory
dbo:abstract
In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct answer; that is, any possible program would sometimes give the wrong answer or run forever without giving any answer. More formally, an undecidable problem is a problem whose language is not a recursive set; see the article Decidable language. There are uncountably many undecidable problems, so the list below is necessarily incomplete. Though undecidable languages are not recursive languages, they may be subsets of Turing recognizable languages: i.e., such undecidable languages may be recursively enumerable. Many, if not most, undecidable problems in mathematics can be posed as word problems: determining when two distinct strings of symbols (encoding some mathematical concept or object) represent the same object or not. For undecidability in axiomatic mathematics, see List of statements undecidable in ZFC.
foaf:isPrimaryTopicOf
n10:List_of_undecidable_problems