# Computability

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

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.