About: Undecidable problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:HigherCognitiveProcess105770664, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FUndecidable_problem

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.

AttributesValues
rdf:type
rdfs:label
  • معضلة غير قابلة للقرار
  • Problema indecidible
  • Undecidable problem
  • Problem nierozstrzygalny
  • Problema indecidível
  • Алгоритмически неразрешимая задача
  • Алгоритмічно нерозв'язна задача
rdfs:comment
  • في نظرية الحاسوبية ونظرية التعقيد الحسابي، معضلة غير قابلة للقرار هي ، حيث يستحيل إنشاء خوارزمية وحيدة، تجيب دائما وبصفة صحيحة، بنعم أو لا على المعضلة المطروحة. انظر إلى مبرهنات عدم الاكتمال لغودل.
  • 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.
  • В теории вычислимости алгоритмически неразрешимой задачей называется задача, имеющая ответ да или нет для каждого объекта из некоторого множества входных данных, для которой (принципиально) не существует алгоритма, который бы, получив любой возможный в качестве входных данных объект, останавливался и давал правильный ответ после конечного числа шагов.
  • В теорії обчислюваності алгоритмічно нерозв'язною задачею називається задача, що має відповідь так чи ні для кожного об'єкта з деякої множини вхідних даних, для якої (принципово) не існує алгоритму, який би, отримавши будь-який можливий як вхідні дані об'єкт, зупинявся і давав правильну відповідь після кінцевого числа кроків.
  • 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.
  • 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).
  • 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.
rdfs:seeAlso
foaf:isPrimaryTopicOf
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git51 as of Sep 16 2020


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3319 as of Dec 29 2020, on Linux (x86_64-centos_6-linux-glibc2.12), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2021 OpenLink Software