List of undecidable problems (original) (raw)
Em Teoria da Computabilidade, o Problema indecidível é um problema em que é impossível construir um algoritmo que sempre responde sim ou não, ele pode não responder ou responder errado. Mais formalmente, um problema indecidível é o problema em que a linguagem não é um conjunto recursivo; veja Decidibilidade. Existem incontáveis problemas indecidíveis, por isso essa lista é incompleta. Apesar de linguagens indecidíveis não serem recursivas, eles podem ser subconjuntos de linguagens Turing-reconhecíveis, ou seja, muitas linguagens indecidíveis podem ser recursivamente enumeráveis.
| Property | Value |
|---|---|
| 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. (en) Em Teoria da Computabilidade, o Problema indecidível é um problema em que é impossível construir um algoritmo que sempre responde sim ou não, ele pode não responder ou responder errado. Mais formalmente, um problema indecidível é o problema em que a linguagem não é um conjunto recursivo; veja Decidibilidade. Existem incontáveis problemas indecidíveis, por isso essa lista é incompleta. Apesar de linguagens indecidíveis não serem recursivas, eles podem ser subconjuntos de linguagens Turing-reconhecíveis, ou seja, muitas linguagens indecidíveis podem ser recursivamente enumeráveis. (pt) 這是一個不可判定问题列表。 (zh) |
| dbo:wikiPageExternalLink | https://mathoverflow.net/q/11540 |
| dbo:wikiPageID | 1188090 (xsd:integer) |
| dbo:wikiPageLength | 12209 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124084771 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Pushdown_automaton dbr:Entscheidungsproblem dbc:Lists_of_problems dbr:Mortality_(computability_theory) dbr:Partially_observable_Markov_decision_process dbr:Homeomorphic dbr:Vector_(mathematics_and_physics) dbr:Computability_theory dbr:Context-free_grammar dbr:Matiyasevich's_theorem dbr:Trakhtenbrot's_theorem dbr:Conjugacy_problem dbr:Conway's_Game_of_Life dbr:Rule_110 dbr:Logic_of_graphs dbr:Magic:_The_Gathering dbr:Computational_problem dbr:Fundamental_group dbr:Horn_clause dbr:Post_correspondence_problem dbr:Tag_system dbr:MathOverflow dbr:Busy_beaver dbc:Undecidable_problems dbr:Type_checking dbr:Semigroup dbr:Alan_Turing dbr:5-manifold dbr:Air_travel dbr:Fare dbr:Hilbert's_tenth_problem dbr:Kolmogorov_complexity dbr:Simplicial_complex dbr:Reduction_(complexity) dbr:Halting_problem dbc:Computability_theory dbc:Theory_of_computation dbr:Lambda_calculus dbr:Word_problem_for_groups dbr:Manifold dbr:Polynomial dbr:Group_isomorphism_problem dbr:Ordinary_differential_equation dbc:Mathematics-related_lists dbr:Recursive_set dbr:Word_problem_(mathematics) dbr:Turing_machine dbr:Undecidable_problem dbr:Wang_tile dbr:Type_inference dbr:Lists_of_problems dbr:Richardson's_theorem dbr:Mortal_matrix_problem dbr:Integer_matrices dbr:Rice's_theorem dbr:Subset dbr:Zero_matrix dbr:Uncountable_set dbr:Risch_algorithm dbr:List_of_statements_undecidable_in_ZFC dbr:Spectral_gap_(physics) dbr:Simply_connected dbr:Minsky_machine dbr:Decidable_language dbr:Second-order_lambda_calculus dbr:List_of_unsolved_problems |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cite_book dbt:Cite_journal dbt:Main dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Lists_of_problems dbc:Undecidable_problems dbc:Computability_theory dbc:Theory_of_computation dbc:Mathematics-related_lists |
| gold:hypernym | dbr:Problem |
| rdf:type | dbo:Disease |
| rdfs:comment | Em Teoria da Computabilidade, o Problema indecidível é um problema em que é impossível construir um algoritmo que sempre responde sim ou não, ele pode não responder ou responder errado. Mais formalmente, um problema indecidível é o problema em que a linguagem não é um conjunto recursivo; veja Decidibilidade. Existem incontáveis problemas indecidíveis, por isso essa lista é incompleta. Apesar de linguagens indecidíveis não serem recursivas, eles podem ser subconjuntos de linguagens Turing-reconhecíveis, ou seja, muitas linguagens indecidíveis podem ser recursivamente enumeráveis. (pt) 這是一個不可判定问题列表。 (zh) 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) |
| rdfs:label | List of undecidable problems (en) Lista de problemas indecidíveis (pt) 不可判定问题列表 (zh) |
| owl:sameAs | wikidata:List of undecidable problems dbpedia-pt:List of undecidable problems dbpedia-zh:List of undecidable problems https://global.dbpedia.org/id/so4A |
| prov:wasDerivedFrom | wikipedia-en:List_of_undecidable_problems?oldid=1124084771&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:List_of_undecidable_problems |
| is dbo:wikiPageRedirects of | dbr:List_of_undecidable_problem |
| is dbo:wikiPageWikiLink of | dbr:Decision_problem dbr:List_of_impossible_puzzles dbr:Computability dbr:Computability_theory dbr:Complexity_class dbr:Decidability dbr:Fallibilism dbr:RE_(complexity) dbr:Lists_of_problems dbr:Outline_of_logic dbr:Spectral_gap_(physics) dbr:List_of_undecidable_problem |
| is foaf:primaryTopic of | wikipedia-en:List_of_undecidable_problems |