Talk:Hypercomputation/PNDTM

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

where

$Q$ is a finite set of states
$Σ$ is a finite set of symbols (the tape alphabet)
$\iota \in Q$ is the initial state
$\sqcup$ is the blank symbol ( $\sqcup \in \Sigma$ )
$A \subseteq Q$ is the set of accepting states
$\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.
$\leq_A: A \times A \rightarrow \{ 0,1 \}$ is a binary relation which induces a total ordering on A. An accepting state $a \in A$ is said to be preferred to state $b \in A$ iff $b \neq a$ and $b \leq_A a$ .