「非決定性チューリングマシン」の版間の差分

*<math>\delta: Q \backslash A \times \Sigma \rightarrow \left( Q \times \Sigma \times \{L,R\} \right)</math> は遷移関数であり、状態と記号に関する[[関数 (数学)#多変数関数と多価関数|多値価関数]]である。ここで、''L'' はテープヘッドの左シフト、''R'' は右シフトを表す。普通のチューリング機械では遷移関数は多値価ではない。