Definition of a Turing Machine We start with an informal description of a Turing Machine. Such a machine consists of the following: There are k tapes , for some fixed k ≥ 1. Each tape is divided into cells, and is infinite both to the left and to the right. Each cell stores a symbol belonging to a