| http://dbpedia.org/ontology/abstract
|
Problem nierozstrzygalny – problem decyzyj … 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.ednym z nich jest właśnie zdanie 17 Gen r.
, In computability theory and computational … 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.bitrary programs eventually halt when run.
, Nerozhodnutelný problém je v teorii vyčísl … 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.á část z nich jsou rozhodnutelné problémy.
, 不可判定问题是可计算性理论和计算复杂性理论中定义的一类决定性问题，此类问题无法总是用单一算法得出正确的是/否的答案。停机问题是这类问题的一个代表：对于停机问题，没有算法能够正确判定任意程序是否会终止运行。
, В теории вычислимости алгоритмически нераз … В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.вильный ответ после конечного числа шагов.
, Na teoria da computação e na teoria da com … 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. são decidíveis são chamados indecidíveis.
, В теорії обчислюваності алгоритмічно нероз … В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків. відповідь після скінченного числа кроків.
, En teoría de la computabilidad y en teoría … 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.bre un problema conocido como indecidible.
, في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي ، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة. انظر إلى مبرهنات عدم الاكتمال لغودل.
|
| http://dbpedia.org/ontology/wikiPageID
|
15631055
|
| http://dbpedia.org/ontology/wikiPageLength
|
13451
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1120140159
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Word_problem_for_groups +
, http://dbpedia.org/resource/Deductive_system +
, http://dbpedia.org/resource/Max_Dehn +
, http://dbpedia.org/resource/Uncountable_set +
, http://dbpedia.org/resource/Philosophy_of_mathematics +
, http://dbpedia.org/resource/Computer_program +
, http://dbpedia.org/resource/Integer_number +
, http://dbpedia.org/resource/Kruskal%27s_tree_theorem +
, http://dbpedia.org/resource/Kolmogorov_complexity +
, http://dbpedia.org/resource/Group_theory +
, http://dbpedia.org/resource/Abstract_machine +
, http://dbpedia.org/resource/Mathematical_proof +
, http://dbpedia.org/resource/Rice%27s_theorem +
, http://dbpedia.org/resource/Formal_system +
, http://dbpedia.org/resource/Proof_of_impossibility +
, http://dbpedia.org/resource/Whitehead_problem +
, http://dbpedia.org/resource/Soundness +
, http://dbpedia.org/resource/Saharon_Shelah +
, http://dbpedia.org/resource/Algorithmic_information_theory +
, http://dbpedia.org/resource/Algorithm +
, http://dbpedia.org/resource/Complex_plane +
, http://dbpedia.org/resource/Corollary +
, http://dbpedia.org/resource/Halting_problem +
, http://dbpedia.org/resource/Independence_%28mathematical_logic%29 +
, http://dbpedia.org/resource/Natural_numbers +
, http://dbpedia.org/resource/Turing_machine +
, http://dbpedia.org/resource/Consistency_proof +
, http://dbpedia.org/resource/Natural_number +
, http://dbpedia.org/resource/Recursive_set +
, http://dbpedia.org/resource/ZFC +
, http://dbpedia.org/resource/Countably_infinite +
, http://dbpedia.org/resource/Fermat%27s_Last_Theorem +
, http://dbpedia.org/resource/Computable_function +
, http://dbpedia.org/resource/Recursively_enumerable_set +
, http://dbpedia.org/resource/Zermelo%E2%80%93Fraenkel_set_theory +
, http://dbpedia.org/resource/Entscheidungsproblem +
, http://dbpedia.org/resource/Hilbert%27s_tenth_problem +
, http://dbpedia.org/resource/G%C3%B6del%27s_incompleteness_theorem +
, http://dbpedia.org/resource/Truth_value +
, http://dbpedia.org/resource/Formal_language +
, http://dbpedia.org/resource/Gregory_Chaitin +
, http://dbpedia.org/resource/Category:Logic_in_computer_science +
, http://dbpedia.org/resource/Set_theory +
, http://dbpedia.org/resource/Second-order_arithmetic +
, http://dbpedia.org/resource/Axiomatization +
, http://dbpedia.org/resource/Peano_axioms +
, http://dbpedia.org/resource/String_%28computer_science%29 +
, http://dbpedia.org/resource/Category:Computability_theory +
, http://dbpedia.org/resource/Category:Undecidable_problems +
, http://dbpedia.org/resource/Paul_Cohen_%28mathematician%29 +
, http://dbpedia.org/resource/Wicked_problem +
, http://dbpedia.org/resource/Yuri_Matiyasevich +
, http://dbpedia.org/resource/First-order_logic +
, http://dbpedia.org/resource/Ramsey_theorem +
, http://dbpedia.org/resource/Collatz_problem +
, http://dbpedia.org/resource/Paris-Harrington_theorem +
, http://dbpedia.org/resource/Iterate +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/John_Horton_Conway +
, http://dbpedia.org/resource/Continuum_hypothesis +
, http://dbpedia.org/resource/Diophantine_equation +
, http://dbpedia.org/resource/Ramsey_theory +
, http://dbpedia.org/resource/Logic +
, http://dbpedia.org/resource/Topology +
, http://dbpedia.org/resource/Decidability_%28logic%29 +
, http://dbpedia.org/resource/Berry%27s_paradox +
, http://dbpedia.org/resource/Liar_paradox +
, http://dbpedia.org/resource/G%C3%B6del_numbering +
, http://dbpedia.org/resource/Computability_theory +
, http://dbpedia.org/resource/Goodstein%27s_theorem +
, http://dbpedia.org/resource/Axiom_of_choice +
, http://dbpedia.org/resource/Group_%28mathematics%29 +
, http://dbpedia.org/resource/Polynomial +
, http://dbpedia.org/resource/Alan_Turing +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:More_citations_needed +
, http://dbpedia.org/resource/Template:Refimprove_section +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Mathematical_logic +
, http://dbpedia.org/resource/Template:See_also +
, http://dbpedia.org/resource/Template:Main +
, http://dbpedia.org/resource/Template:Short_description +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Undecidable_problems +
, http://dbpedia.org/resource/Category:Logic_in_computer_science +
, http://dbpedia.org/resource/Category:Computability_theory +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Problem +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Undecidable_problem?oldid=1120140159&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Undecidable_problem +
|
| owl:sameAs |
http://ar.dbpedia.org/resource/%D9%85%D8%B9%D8%B6%D9%84%D8%A9_%D8%BA%D9%8A%D8%B1_%D9%82%D8%A7%D8%A8%D9%84%D8%A9_%D9%84%D9%84%D9%82%D8%B1%D8%A7%D8%B1 +
, http://ru.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D0%BD%D0%B5%D1%80%D0%B0%D0%B7%D1%80%D0%B5%D1%88%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0 +
, https://global.dbpedia.org/id/3E6CK +
, http://zh.dbpedia.org/resource/%E4%B8%8D%E5%8F%AF%E5%88%A4%E5%AE%9A%E9%97%AE%E9%A2%98 +
, http://hi.dbpedia.org/resource/%E0%A4%85%E0%A4%A8%E0%A4%BF%E0%A4%B0%E0%A5%8D%E0%A4%A3%E0%A4%A8%E0%A5%80%E0%A4%AF_%E0%A4%AA%E0%A5%8D%E0%A4%B0%E0%A5%89%E0%A4%AC%E0%A5%8D%E0%A4%B2%E0%A4%AE +
, http://pt.dbpedia.org/resource/Problema_indecid%C3%ADvel +
, http://es.dbpedia.org/resource/Problema_indecidible +
, http://fa.dbpedia.org/resource/%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%AA%D8%B5%D9%85%DB%8C%D9%85%E2%80%8C%D9%86%D8%A7%D9%BE%D8%B0%DB%8C%D8%B1 +
, http://cs.dbpedia.org/resource/Nerozhodnuteln%C3%BD_probl%C3%A9m +
, http://rdf.freebase.com/ns/m.03nn3tw +
, http://yago-knowledge.org/resource/Undecidable_problem +
, http://dbpedia.org/resource/Undecidable_problem +
, http://uk.dbpedia.org/resource/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%96%D1%87%D0%BD%D0%BE_%D0%BD%D0%B5%D1%80%D0%BE%D0%B7%D0%B2%27%D1%8F%D0%B7%D0%BD%D0%B0_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0 +
, http://sr.dbpedia.org/resource/%D0%9D%D0%B5%D0%BE%D0%B4%D0%BB%D1%83%D1%87%D0%B8%D0%B2_%D0%B7%D0%B0%D0%B4%D0%B0%D1%82%D0%B0%D0%BA +
, http://bg.dbpedia.org/resource/%D0%9D%D0%B5%D1%80%D0%B5%D1%88%D0%B8%D0%BC_%D0%BF%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC +
, http://www.wikidata.org/entity/Q3502995 +
, http://pl.dbpedia.org/resource/Problem_nierozstrzygalny +
|
| rdf:type |
http://dbpedia.org/class/yago/Thinking105770926 +
, http://dbpedia.org/class/yago/HigherCognitiveProcess105770664 +
, http://dbpedia.org/ontology/Disease +
, http://dbpedia.org/class/yago/Cognition100023271 +
, http://dbpedia.org/class/yago/WikicatFormalTheoriesOfArithmetic +
, http://dbpedia.org/class/yago/Process105701363 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Explanation105793000 +
, http://dbpedia.org/class/yago/Theory105989479 +
, http://dbpedia.org/class/yago/PsychologicalFeature100023100 +
|
| rdfs:comment |
En teoría de la computabilidad y en teoría … 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...ario se detendrá, una vez sea ejecutado...
, В теорії обчислюваності алгоритмічно нероз … В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після скінченного числа кроків. відповідь після скінченного числа кроків.
, В теории вычислимости алгоритмически нераз … В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.вильный ответ после конечного числа шагов.
, Problem nierozstrzygalny – problem decyzyj … 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). nierozstrzygalnym (patrz: problem stopu).
, 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čísl … 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í.po svém spuštění na daných datech zastaví.
, In computability theory and computational … 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.bitrary programs eventually halt when run.
|
| rdfs:label |
Problema indecidible
, معضلة غير قابلة للقرار
, Алгоритмічно нерозв'язна задача
, Problem nierozstrzygalny
, Problema indecidível
, Алгоритмически неразрешимая задача
, Undecidable problem
, Nerozhodnutelný problém
, 不可判定问题
|
| rdfs:seeAlso |
http://dbpedia.org/resource/List_of_statements_independent_of_ZFC +
|
