ABSTRACT
A Turing machine is a simple abstract computational device intended to investigate the extent of what can be computed on a sequential computer. This model enables one to define the cost of an algorithm (e.g., in number of operations) precisely and is the basis for complexity results (e.g., polynomial vs. NP-complete, etc.).
