計算理論 Archives - Scientia Potentia Est

通長在測量複雜度的時候會使用兩種分析方法：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的數量…

圖靈機是由Alan Turing在1936年提出的概念，現今世界上所有的計算機不管是多複雜的架構都可以使用圖靈機的概念設計出來，其主要核心精神如下圖

我們在密碼理論(Theory of Cryptology)又或者計算理論(Theory of Computation)裡需要去測量輸入的整數複雜度，通常會用整數的長度(bits)當作標準。

Scientia Potentia Est