About: List of undecidable problems

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

About: List of undecidable problems Goto Sponge NotDistinct Permalink

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

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.

Attributes	Values
rdf:type	disease
rdfs:label	List of undecidable problems (en)
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. (en)
dbp:wikiPageUsesTemplate	dbt:Citation dbt:Cite_book dbt:Cite_journal dbt:Reflist dbt:Short_description
Subject	Computability theory Theory of computation Undecidable problems Lists of problems Mathematics-related lists
gold:hypernym	Problem
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/List_of_undecidable_problems?oldid=1036516846&ns=0
Wikipage page ID	1188090 (xsd:integer)
page length (characters) of wiki page	12228 (xsd:nonNegativeInteger)
Wikipage revision ID	1036516846 (xsd:integer)
Link from a Wikipage to another Wikipage	List of statements independent of ZFC Lists of problems Lists of unsolved problems Logic of graphs Magic: The Gathering Risch algorithm Tag system Uncountable set Undecidable problem 5-manifold Air travel Alan Turing Semigroup Turing machine Busy beaver Computability theory Theory of computation Undecidable problems Lists of problems Mathematics-related lists Diophantine set Hilbert's tenth problem Post correspondence problem Word problem (mathematics) Word problem for groups Zero matrix Horn clause Pushdown automaton Rule 110 Computability theory Computable set Computational problem Conjugacy problem Context-free grammar Conway's Game of Life Homeomorphism Mortality (computability theory) Ordinary differential equation Partially observable Markov decision process Rice's theorem Spectral gap (physics) Wang tile Entscheidungsproblem Fundamental group System F Fare Group isomorphism problem Halting problem Integer matrix Lambda calculus Manifold Type inference Type system Vector (mathematics and physics) Subset Trakhtenbrot's theorem Kolmogorov complexity MathOverflow Polynomial Recursive language Reduction (complexity) Register machine Richardson's theorem Simplicial complex Simply connected space
has 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/List_of_undecidable_problems
is Wikipage redirect of	List of undecidable problem
is Link from a Wikipage to another Wikipage of	Lists of problems Decidability Decision problem Complexity class Computability Computability theory Fallibilism List of undecidable problem
is foaf:primaryTopic of	http://en.wikipedia.org/wiki/List_of_undecidable_problems

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 (72 GB total memory, 890 MB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software