Non-Computable Problems - Research Article from World of Computer Science

This encyclopedia article consists of approximately 2 pages of information about Non-Computable Problems.
This section contains 452 words
(approx. 2 pages at 300 words per page)
Buy the Non-Computable Problems Encyclopedia Article

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...

(read more)

This section contains 452 words
(approx. 2 pages at 300 words per page)
Buy the Non-Computable Problems Encyclopedia Article
Copyrights
Gale
Non-Computable Problems from Gale. ©2005-2006 Thomson Gale, a part of the Thomson Corporation. All rights reserved.
Follow Us on Facebook