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
• $\Sigma$ 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$.