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

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

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-eshttp://es.dbpedia.org/resource/
n29https://global.dbpedia.org/id/
n28http://hi.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-srhttp://sr.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-cshttp://cs.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
dbpedia-arhttp://ar.dbpedia.org/resource/
owlhttp://www.w3.org/2002/07/owl#
dbpedia-zhhttp://zh.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
dbpedia-bghttp://bg.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Undecidable_problem
rdf:type
yago:Abstraction100002137 owl:Thing yago:Theory105989479 yago:Thinking105770926 yago:Process105701363 yago:PsychologicalFeature100023100 yago:HigherCognitiveProcess105770664 yago:Cognition100023271 yago:Explanation105793000 dbo:Disease yago:WikicatFormalTheoriesOfArithmetic
rdfs:label
Алгоритмічно нерозв'язна задача Problema indecidible Problema indecidível 不可判定问题 Алгоритмически неразрешимая задача Nerozhodnutelný problém Undecidable problem Problem nierozstrzygalny معضلة غير قابلة للقرار
rdfs:comment
في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي ، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة. انظر إلى مبرهنات عدم الاكتمال لغودل. Na teoria da computação e na teoria da complexidade computacional, um problema indecidível é um problema de decisão em que é impossível construir um algoritmo que sempre responde corretamente sim ou não. Nerozhodnutelný problém je v teorii vyčíslitelnosti a teorii složitosti takový rozhodovací problém, pro který není možné zkonstruovat algoritmus, který vždy vydá správnou odpověď ano nebo ne. Příkladem je problém zastavení: lze dokázat, že neexistuje žádný algoritmus, který o libovolném programu rozhodne, zda se po svém spuštění na daných datech zastaví. Problem nierozstrzygalny – problem decyzyjny, dla którego nie istnieje algorytm, który po skończonej liczbie kroków i dla dowolnych danych wejściowych jednoznacznie odpowie tak lub nie. Turing w 1936 roku wykazał, że udzielenie odpowiedzi na pytanie, czy maszyna Turinga o numerze wykonując działania nad liczbą zakończy kiedyś swoją pracę, czy też przewidziany dla niej algorytm będzie realizowany w nieskończoność, jest problemem nierozstrzygalnym (patrz: problem stopu). En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de sí o no correcta. El problema de la parada es un ejemplo: no existe algoritmo que determine de manera correcta si un programa arbitrario se detendrá, una vez sea ejecutado... 不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків. В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.
rdfs:seeAlso
dbr:List_of_statements_independent_of_ZFC
dcterms:subject
dbc:Computability_theory dbc:Logic_in_computer_science dbc:Undecidable_problems
dbo:wikiPageID
15631055
dbo:wikiPageRevisionID
1120140159
dbo:wikiPageWikiLink
dbr:Hilbert's_tenth_problem dbr:Logic dbr:Paul_Cohen_(mathematician) dbr:Recursively_enumerable_set dbr:Soundness dbr:Deductive_system dbr:Ramsey_theorem dbc:Undecidable_problems dbr:Ramsey_theory dbr:Formal_language dbr:Alan_Turing dbr:Set_theory dbr:Saharon_Shelah dbr:Proof_of_impossibility dbr:Computable_function dbr:Goodstein's_theorem dbr:Corollary dbr:John_Horton_Conway dbr:Second-order_arithmetic dbr:ZFC dbr:Berry's_paradox dbr:Computability_theory dbr:Polynomial dbr:String_(computer_science) dbr:Gödel's_incompleteness_theorem dbr:Natural_number dbr:Natural_numbers dbr:Gregory_Chaitin dbr:Algorithmic_information_theory dbr:Group_(mathematics) dbr:Zermelo–Fraenkel_set_theory dbr:Fermat's_Last_Theorem dbr:Formal_system dbr:Algorithm dbr:Halting_problem dbr:Abstract_machine dbr:Mathematical_proof dbr:Peano_axioms dbr:Axiom_of_choice dbr:Complex_plane dbr:Paris-Harrington_theorem dbr:Axiomatization dbr:Topology dbr:Continuum_hypothesis dbc:Computability_theory dbr:Collatz_problem dbr:Uncountable_set dbr:Consistency_proof dbr:First-order_logic dbr:Independence_(mathematical_logic) dbr:Yuri_Matiyasevich dbr:Kolmogorov_complexity dbr:Iterate dbr:Entscheidungsproblem dbr:Truth_value dbr:Kruskal's_tree_theorem dbr:Countably_infinite dbr:Group_theory dbr:Diophantine_equation dbc:Logic_in_computer_science dbr:Rice's_theorem dbr:Liar_paradox dbr:Turing_machine dbr:Computational_complexity_theory dbr:Computer_program dbr:Philosophy_of_mathematics dbr:Word_problem_for_groups dbr:Gödel_numbering dbr:Max_Dehn dbr:Wicked_problem dbr:Integer_number dbr:Decision_problem dbr:Recursive_set dbr:Whitehead_problem dbr:Decidability_(logic)
owl:sameAs
dbpedia-cs:Nerozhodnutelný_problém freebase:m.03nn3tw yago-res:Undecidable_problem dbpedia-bg:Нерешим_проблем dbpedia-es:Problema_indecidible dbpedia-uk:Алгоритмічно_нерозв'язна_задача dbpedia-zh:不可判定问题 dbpedia-pt:Problema_indecidível dbpedia-sr:Неодлучив_задатак dbpedia-ar:معضلة_غير_قابلة_للقرار dbpedia-pl:Problem_nierozstrzygalny dbpedia-fa:مسئله_تصمیم‌ناپذیر wikidata:Q3502995 n28:अनिर्णनीय_प्रॉब्लम n29:3E6CK dbpedia-ru:Алгоритмически_неразрешимая_задача
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Reflist dbt:Refimprove_section dbt:Main dbt:More_citations_needed dbt:See_also dbt:Mathematical_logic
dbo:abstract
Problem nierozstrzygalny – problem decyzyjny, dla którego nie istnieje algorytm, który po skończonej liczbie kroków i dla dowolnych danych wejściowych jednoznacznie odpowie tak lub nie. Turing w 1936 roku wykazał, że udzielenie odpowiedzi na pytanie, czy maszyna Turinga o numerze wykonując działania nad liczbą zakończy kiedyś swoją pracę, czy też przewidziany dla niej algorytm będzie realizowany w nieskończoność, jest problemem nierozstrzygalnym (patrz: problem stopu). Innym przykładem problemu nierozstrzygalnego jest tzw. zdanie Gödla o postaci 17 Gen r (generalizacja {kwantyfikator ogólny} formuły r względem zmiennej z numerem 17). Jest to zdanie posiadające tę własność, że ani ono, ani jego negacja nie dają się formalnie dowieść. Zdanie nierozstrzygalne powstało w wyniku odwzorowania antynomii logicznej (zwanej antynomią Richarda) poprzez tak zwaną arytmetyzacją języka klasycznego rachunku zdań. Arytmetyzacja języka pozwala na odwzorowanie relacji logicznych jakie zachodzą między zdaniami w relacje arytmetyczne między liczbami stanowiącymi numery tych zdań. Dzięki temu zamiast o relacjach logicznych można mówić o relacjach arytmetycznych. Istnienie zdania 17 gen r jest powodem nierozstrzygalności arytmetyki, uważanej do czasów Gödla za system rozstrzygalny, to znaczy taki, w którym prawdziwość każdego twierdzenia można rozstrzygnąć w oparciu o skończony zbiór kryteriów. Inaczej mówiąc, zbiór twierdzeń arytmetycznych jest nieobliczalny, co znaczy, że nie można w skończonej ilości kroków rozstrzygnąć, czy dany element tego zbioru, będący twierdzeniem arytmetycznym, jest, czy nie jest elementem zbioru twierdzeń. Tymczasem zbiór dowodów systemu formalnego jest obliczalny, ponieważ w skończonej ilości kroków można rozstrzygnąć, czy dany ciąg napisów jest, czy nie jest dowodem danego twierdzenia. Tak więc zbiór zdań prawdziwych nie pokrywa się ze zbiorem twierdzeń dowodzonych przez system. Wiemy bowiem, że istnieją zdania prawdziwe, których nie da się dowieść w tym systemie. Jednym z nich jest właśnie zdanie 17 Gen r. Na teoria da computação e na teoria da complexidade computacional, um problema indecidível é um problema de decisão em que é impossível construir um algoritmo que sempre responde corretamente sim ou não. Um problema de decisão é qualquer questão arbitrária de sim-ou-não sobre um conjunto infinito de entradas. Por causa disto, é comum definir o problema de decisão de maneira equivalente como: o conjunto de entradas para o qual o problema retorna sim. Estas entradas podem ser números naturais, mas também podem ser outros valores de outros tipos, como cadeias de uma linguagem formal. Usando alguma codificação, tal como uma numeração de Gödel, as cadeias podem ser codificadas como números naturais. Para manter a definição de formalidade simples, ela é colocada em termos de subconjuntos dos números naturais. Formalmente, um problema de decisão é um subconjunto dos números naturais. O problema correspondente de maneira informal é o de se decidir se um dado número está no conjunto. Um problema de decisão A é chamado decidível ou efetivamente solúvel se A é um conjunto recursivo. Um problema é chamado parcialmente decidível, semidecidível, solúvel, ou provável se A é um conjunto recursivamente enumerável. Problemas parcialmente decidíveis e outros problemas que não são decidíveis são chamados indecidíveis. В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов. En teoría de la computabilidad y en teoría de la complejidad computacional, un problema indecidible es un problema de decisión para el cual es imposible construir un algoritmo que siempre conduzca a una respuesta de sí o no correcta. El problema de la parada es un ejemplo: no existe algoritmo que determine de manera correcta si un programa arbitrario se detendrá, una vez sea ejecutado... Un problema de decisión es cualquier pregunta arbitraria de sí o no en un conjunto infinito de entradas. Por ello es tradicional definir el problema de decisión como equivalente al conjunto de entradas para las que el problema retorna sí. Estas entradas pueden ser números naturales, o bien valores de otro tipo, tales como cadenas de un lenguaje formal. Mediante alguna codificación, tal como una numeración de Gödel, las cadenas se pueden codificar como números naturales. Así, un problema de decisión informalmente expresado en términos de un lenguaje formal es también equivalente a un conjunto de números naturales. Para mantener simple la definición formal, se expresa en términos de subconjuntos de los números naturales. Formalmente, un problema de decisión es un subconjunto de los números naturales. El problema informal correspondiente consiste en decidir si un número dado está en el conjunto. A un problema de decisión A, si A es un conjunto recursivo, se le denomina decidible, o efectivamente solucionable. Si A es un conjunto recursivamente enumerable, el problema es parcialmente decidible, semidecidible, solucionable, o demostrable. A problemas parcialmente decidibles y a los no decidibles se les califica de indecidibles. Para demostrar que un problema es indecidible, generalmente se toma un problema que ya se ha demostrado que lo es y se construye una transformación que lo reduce a una instancia del nuevo problema. Se concluye que no puede existir un algoritmo para decidir sobre el nuevo problema dado que ese algoritmo serviría también para decidir sobre un problema conocido como indecidible. Nerozhodnutelný problém je v teorii vyčíslitelnosti a teorii složitosti takový rozhodovací problém, pro který není možné zkonstruovat algoritmus, který vždy vydá správnou odpověď ano nebo ne. Příkladem je problém zastavení: lze dokázat, že neexistuje žádný algoritmus, který o libovolném programu rozhodne, zda se po svém spuštění na daných datech zastaví. Protože pojem algoritmus není přesně definován, tvrzení o existenci nerozhodnutelných problémů zpravidla používají nějakou dobře definovanou formu algoritmu, např. Turingův stroj. Na druhou stranu princip jejich důkazu (důkaz diagonalizací) vychází ze zjištění, že existuje mnoho problémů a jen určitá část z nich jsou rozhodnutelné problémy. 不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。 В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків. In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي ، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة. انظر إلى مبرهنات عدم الاكتمال لغودل.
gold:hypernym
dbr:Problem
prov:wasDerivedFrom
wikipedia-en:Undecidable_problem?oldid=1120140159&ns=0
dbo:wikiPageLength
13451
foaf:isPrimaryTopicOf
wikipedia-en:Undecidable_problem