We define a preferential non-deterministic Turing machine as a 7-tuple ${\displaystyle M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta ,\leq _{A})}$

where

• ${\displaystyle Q}$ is a finite set of states
• ${\displaystyle \Sigma }$ is a finite set of symbols (the tape alphabet)
• ${\displaystyle \iota \in Q}$ is the initial state
• ${\displaystyle \sqcup }$ is the blank symbol (${\displaystyle \sqcup \in \Sigma }$)
• ${\displaystyle A\subseteq Q}$ is the set of accepting states
• ${\displaystyle \delta :Q\backslash A\times \Sigma \rightarrow \left(Q\times \Sigma \times \{L,R\}\right)}$ is a relation called the "transition function", where L is left shift and R is right shift. \delta associates each combination of a non-accepting state and a tape symbol with one or more succesor states, tape symbols to be written, and L/R movements for the tape head.
• ${\displaystyle \leq _{A}:A\times A\rightarrow \{0,1\}}$ is a binary relation which induces a total ordering on A. An accepting state ${\displaystyle a\in A}$ is said to be preferred to state ${\displaystyle b\in A}$ iff ${\displaystyle b\neq a}$ and ${\displaystyle b\leq _{A}a}$.