>>1
形式的に書くと、こんな感じかな。

拡張したチューリングマシン = {Tape, State, Position, Delta, Lambda, Mu}
Tape: Array of Number
State: Integer
Head-Position: Integer
Delta = State * Tape[Position] -> Number
Lambda = State * Tape[Position] -> State
Mu = State * Position -> {-1, 0, 1}
Transition = {Tape(n), State(n), Position(n)} ->
{
Tape(n)[-Infinity .. Position(n) - 1] .. Delta(State(n), Tape(n)[Position(n)]) .. Tape(n)[Position(n) + 1 .. Infinity],
Lambda(State(n), Tape(n)[Position(n)]),
Position(n) + Mu(State(n), Position(n))
}
但しIntegerは可算無限集合、Numberは非可算無限集合、Arrayは高々可算無限長の配列とする。