Non-Computable Problems
Computational Complexity Theory is the discipline of recognising solvable problems that are intractable in the sense that no efficient algorithm exists to solve them. Problems that computational processes are intended to solve can be divided into "decision problems," "functions," and "relations." It is possible to reformulate both decision problems and relations functions, which means that effectively computability can be reduced to solving function problems.
A function is considered "computable" if there exists an algorithm for calculating the function that for any given legal combination of input values produces the correct result within a finite time.
In 1936, English mathematician Alan Turing published a paper called "On computable numbers, with an application to the Entscheidungsproblem [decision problem]." Turing proposed a simple abstract computing machine, based on a notional mathematician with a pencil, an eraser, and a stack of paper. Turing stated that any function is computable if it is computable by one of these machines. He then investigated if there were any mathematical problems that such a machine would be unable to solve. These abstract machines are now called "Turing machines."
Turing's 1936 paper concluded that there is a set of well-defined problems that cannot be solved by any computational procedure. If these problems are formulated as functions, they are called "non-computable functions," and if they are formulated as predicates, which are problems that are presented as assertions with the only possible answers being "true" or "false," they are called "undecidable."
Turing said, effectively, that a function is non-computable if there exists no Turing machine that can compute it. Turing's assertion has been proven correct: there are in fact problems that cannot be answered by algorithmic means no matter for how long the algorithm is allowed to run.
Turing proved his thesis by demonstrating that the "halting problem" is undecidable. The halting problem is formally stated as: "Given a Turing machine M and an initial tape T, does M halt when started on tape T?" A more useful way of stating this for computer scientists is: "Given a program P and a string x, does P halt on input x?" Informally the question is: "Is it possible to predict whether a given computation will terminate?"
And in his paper, Turing proved that the answer is unequivocally "no." For computer programmers and computer scientists this means that it is impossible to write a computer program that can tell if any arbitrary program will ever terminate.
As many problems can be recast in terms of the halting problem, this means that computer scientists know there are a lot of problems that computers can never solve. Nevertheless, there are compromises in the form of partial solutions and heuristic algorithms that usually, but not always work and nearly always give the right answer.
This is the complete article, containing 452 words
(approx. 2 pages at 300 words per page).
