### Some basic definition:

**Language**: a language is a set of strings. If you have an alphabet, such as , then is the set of all words containing only the symbols in . For example, is the set of all binary sequences of any length.

Turing machine: A Turing machine is a 7-tuple, where are all finite sets and

- is the set of states,
- is the input alphabet not containing the blank symbol ,
- is the tape alphabet, where and ,
- is the transition function,
- is the start state,
- is the accept state, and
- is the reject state, where