List_of_undecidable_problem List_of_undecidable_problem

List of undecidable problem - Definition and Overview

In computability theory, an undecidable problem is a problem whose language is not a recursively enumerable set. More informally, such problems cannot be solved by computers; see decidability. This is a list of undecidable problems.

Problems related to abstract machines

  • the halting problem
  • Rice's theorem states that all non-trivial properties of computer programs are undecidable.
  • Determining if a context-free grammar generates all possible strings, or if it is ambiguous
  • Determining if two context-free grammars generate some identical string, if they generate the same set of strings, or if one generates all the strings generated by the other

Other problems

See also: list of statements undecidable in ZFC

Example Usage of undecidable

fantasma: On Formally undecidable Propositions of Principia Mathematica and Related Systems.
ez_aisah: SHUCKS!!! I TOTALLY FORGOT ABT YUNA'S CONCERT TONITE....BZ UPLOADING VIDEOS WHOLE DAY!!! STILL undecidable ABT BB/IPHONE!!! HAIZ.....
Copyright 2009 WordIQ.com - Privacy Policy  :: Terms of Use  :: Contact Us  :: About Us
This article is licensed under the GNU Free Documentation License. It uses material from the this Wikipedia article.