Category: 

What Is an Undecidable Problem?

Article Details
  • Written By: Mary McMahon
  • Edited By: Shereen Skola
  • Last Modified Date: 14 November 2016
  • Copyright Protected:
    2003-2016
    Conjecture Corporation
  • Print this Article
Free Widgets for your Site/Blog
Snake charmers get snakes to “dance” because of the movement of their flute-like instruments, not their music.  more...

December 4 ,  1945 :  The United States Senate approved of US participation in the United Nations.  more...

An undecidable problem is a question that cannot be resolved with the use of one algorithm. This is a subject of interest in mathematics and computer programming, where the undecidable problem has significant implications. Researchers with an interest in Turing machines, for example, have tackled the issue of the halting problem, looking at when computer programs stop, versus running infinitely. As with other challenges in mathematics, considerable research surrounds ways to get around undecidable problems, in addition to identifying new problems for more evaluation and study.

This subject involves decision problems, questions with yes or no answers. In mathematics, these are often presented in the form of formulas. A simple example might be “For any real numbers, is X evenly divisible by Y?” This is a decidable problem, because if the computer is given any values for X or Y, it can use an algorithm to answer the question. More complex problems may not be solvable with a single algorithm for all possible values.

In these cases, an algorithm might be accurate for some answers, but could be incapable of answering for other values. Given some values, the algorithm could move through a series of steps to determine whether the answer to the question was yes or no. In other cases, it wouldn’t be able to do so because it would lack the necessary information. This is a known issue with some problems involving matrices, complex analysis, and certain other functions.

Ad

Identification of an undecidable problem can occur in the context of math and computer science research. Once a problem is believed to be undecidable, researchers can apply a variety of tactics to disprove this theory. This can include developing algorithms that work for some values, discussing the specifics of the problem that make it impossible to treat effectively with an algorithm for all values, and related activities. Mathematics and computer science publications may discuss the latest progress in this field with examples of algorithms researchers have used to explore the boundaries of an undecidable problem.

Far from being a topic of theoretical interest only, the undecidable problem can have important implications for the real world. For example, some computer viruses present systems with undecidable problems. The system’s attempt to work through the problem can eat through resources, causing the system to freeze or creating system vulnerabilities. Similarly, technicians might cause a problem with a system by unwittingly presenting it with a problem it cannot solve. They might need to terminate a program or operation, which could result in data loss.

Ad

You might also Like

Recommended

Discuss this Article

Post your comments

Post Anonymously

Login

username
password
forgot password?

Register

username
password
confirm
email