CPSC 201 Lecture 9: Turing Machine Notes
4 Oct 2016
School
Department
Course
Professor
Document Summary
As part of the question of what is computable, alan turing created one of the formal definitions of computation- the turing machines. Turing defines that the machine has an infinitely long tape broken up into squares. Each square can contain a symbol- the most commonly used ones include 1, 0, and blanks (which are often represented with a b in programming. Though the tape can be infinitely long, in general, we can only represent a finite number of squares. The machine is really just the read/write head which is position at one particular square and the symbol on that square of tape is referred to as the current symbol. Only the current symbol may be read or written and to get to other symbols, the machines moves l or r, one square at a time. Following a set of instructions, the machine can only move one place at a time.
