Computability and Complexity/Computability
Computability[edit | edit source]
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 can be thought of as very basic situations or questions.
In this day and age we are surrounded by advanced computers which work at dizzying speeds; it is easy to assume that given enough memory or processing power a computer could compute any problem. However, through mathematics we can prove that there are certain problems which simply do not have clear solutions. For example: when given the problem "What is the last digit of Pi?" it is impossible to find a solution because Pi is infinitely long.
When measuring the "difficulty" of computing a solution, a concept known as "Automata Theory" can be helpful both for calculations as well as comprehension of the problem. Automata Theory will be covered further on in this book - it is a central component in understanding complexity.
Automata Theory[edit | edit source]
When discovering what may or may not be computable, it is helpful - and indeed, perhaps necessary - to construct models which express the logic behind our computation. Models allow us to plot out exactly how a problem was answered, and allows us to examine every step of the process.
Automata are one kind of model, we can think of them as a kind of machine which represents a problem (such as what is 2 + 2) and then when given some input ( 4 ) runs through a series of steps and either accepts the input as valid, or denies it. This idea (does the input match the given constraints?) is very powerful - and when used sequentially can solve all computable problems.
Automata theory was influenced by the functionalist philosophical movement. Rather than considering mathematics as utilizing numbers which in turn represent values, functionalists preferred to think of numbers as merely being symbols which were manipulated by various rules. When we examine Automata you will see many letters rather than numbers - this is because we are regarding the letters as symbols which themselves hold no inherent importance, and are simply manipulated by the rules we supply. This concept will being to make more sense as you grow more comfortable working with Automata.
*d.png)
The image shown at right is an example of an Automata. It accepts -AKA returns 'true' - if the input matches the constraints a(bc)*d (one 'a' followed by any number of 'bc's and then a single 'd').
Let's examine this image. Each circle is known as a state, each state is given a name qN where n is the identifying number. If we imagine Automata as representing our own mental arithmetic, we can think of each state as being what step in our logical thought pattern we are in. The arrows which point to the different circles are known as "transitions" and lead from one state to another if certain conditions are met. Depending on what kind of Automata you are working with these conditions may vary. In the example given, the only constraint is that our model sees the specified character at the point in the input currently being examined.
For a(bc)*d, the first thing we should check is whether or not the input contains an 'a' at the beginning. If we see an a, we move to the second state. ....