Let be a function that takes a string of bits…and outputs either 0 or 1. An algorrthm for computing is a set of mechanical rules, such that by following them we can compute given any input . The set of rules being followed is fixed (i.e. the same rule must work for all possible input) though each rule in this set may be applied arbitrarily many times. Each rule involves one or more of the following ‘elementary’ operations:
- Read a bit of the input.
- Read a bit…from the scratch pad or working space we allow the algorithm to use.
Based on the values read,
- Write a bit/symbol to the scratch pad.
- Either stop and output 0 or 1, or choose a new rule from the set that will be applied next.
Finally, the running time is the number of these basic operations performed.