
時間複雜度
通長在測量複雜度的時候會使用兩種分析方法:Worst-case analysisAverage-case analysis定義一個M是Deterministic Turing Machine並且會根據輸入決定停止規範M的執行時間或者時間複雜度可以表示成一個function...

其他種圖靈機
讓Turing Machine擁有多組tape
\[ \delta: Q \times \Gamma^{k} \rightarrow Q \times \Gamma^{k} \times {L, R}^{k}, k \]: tapes的數量