Solving Computational Problems

The term solvable is defined, in algorithmic terms, as “a computational problem that can be solved by a Turing machine” (Black, 2004).

This means that a solvable problem must follow a certain logical progression with rules or constraints that do not contradict each other (there is a feasible solution) and a solution must me obtainable given the resources used (so as not to cause a fault condition in the processing) and that the solution must be confidently correct (i.e. without any lack of statistical significance). Without all of these aspects it is unlikely that any problem could claim to be solvable as there exists no algorithm that is capable of predicting whether a solution exits. Turning provided this conclusion by determining whether a program was neither self-terminating nor not self-terminating (i.e. halting).

The halting problem which asks whether the process will halt when it is given an input. Turing has shown that the halting problem is not decidable, hence unsolvable. This assumes that the Turing machine understands the input, which presents a second unsolvable problem, which is more complex still, if the input language is not understood. Both problems are unsolvable in the context that they are beyond the capability of any algorithmic system.

We can conclude that some problems are unsolvable although heuristic or partial solutions are possible. My opinion on what it would take for someone to convince me that a solution exists to an unsolvable problem brings Gödel’s Dichotomy to mind. This explores the notions of mind versus machine (and algorithmic solutions) and what is conceivable within the confines of current logic and what is possible with the mind and how these may develop. For although it would take a great deal to convince me that a currently unsolvable has a solution, I cannot quite state that currently unsolvable problems may not be solved in the future by a currently, as yet undeveloped system or algorithm.

This would suggest that all unsolvable problems are potentially unsolved problems waiting for future consideration (Wolfram MathWorld, n.d.) and, like many problems considered unsolvable in the past, the development of algorithmic techniques and systems has produced solutions.

References

Hodges, A. (1997) Alan Turing Scrapbook: Turing Machines [Online]. Available from http://www.turing.org.uk/turing/scrapbook/machine.html (Accessed 22 November 2009).

Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 9 August 2004. Available from: http://www.itl.nist.gov/div897/sqg/dads/HTML (Accessed: 22 Nov 2009)

Glenn, J. (2009) Computer Science: An Overview. 10th ed. Boston: Pearson Education.

Feferman, S. (2006) Philosophia Mathematica. Are There Absolutely Unsolvable Problems? Gödel’s Dichotomy [Online]. Available from: http://math.stanford.edu/~feferman/papers/dichotomy.pdf (Accessed: 21 Nov 2009)

Wolfram MathWorld Unsolved Problems [Online]. Available from: http://mathworld.wolfram.com/UnsolvedProblems.html (Accessed: 20 Nov 2009)