Computability and Complexity/Computability
From Wikibooks, the open-content textbooks collection
[edit] Computability
This page is in need of development.
Computability Theory is the branch of computer science concerned with determining whether a certain problem is solvable. Problems are very basic situations in which a condition is tested, and solubility is the characteristic of the problem that shows the condition to be true or false, that is returns a 1 or a 0 respectively. It is easy to think that given the amazing abilities of computers in this day at age that no problem would be unsolvable, but certain problems, even given an idealized computer with infinite resources, simply have no clear answers. A simple example in everyday terms would be to ask a computer for the last digit of pi, though this is not technically a "problem" as computability theory uses it. The amount of theoretical time for a computer or "automoton" to solve a problem is known as computational complexity and will be discussed at a later point in this book.
It was mentioned that computers may be called automotons. In truth they are but a real world model of a type of automoton called a deterministic finite state machine. These "machines" are actually imaginary devices or abstractions that computer scientist use to determine a problems solubility....
