We define a preferential non-deterministic Turing machine as a 7-tuple
where
is a finite set of states
is a finite set of symbols (the tape alphabet)
is the initial state
is the blank symbol (
)
is the set of accepting states
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.
is a binary relation which induces a total ordering on A. An accepting state
is said to be preferred to state
iff
and
.