Trending News: Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測 問題分類異常檢測 方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週五. 5 月 3rd, 2024
Trending News: Palo Alto Firewall URL過濾 以及 Application Block Page群NP-Completeness異常檢測 問題分類異常檢測 方法評估異常檢測簡介 Anomaly Detection高斯消去法Vectors時間複雜度不同的Turing MachineTuring Machine熵 Entropy資訊測量符號Mutual InformationPalo Alto Firewall 防火牆 Policy 政策 設定Palo Alto 防火牆 NAT (Network Address Translation) 設定《研究生完全求生手冊》讀後心得：研究生必須學會的方法、秘訣與淺規則密碼系統 RSA 攻防中國餘式定理 Chinese Remainder Theorem 與 同構 Isomorphism 特性Square Multiply 演算法尤拉函數 Euler’s totient function整數複雜度量測如何 安裝 Palo Alto VM《長銷》讀後心得：內容、定位、行銷、平台，從個人創作到企業經營都要懂的打造經典之道
週五. 5 月 3rd, 2024

不同的Turing Machine

目錄

Multi-tape Turing Machine

在單一的tape裡面存在多組tape，另外每一個tape都由各自的讀寫頭來進行控制，在規範各個tape之間使用的alphabet即可。

Non-Deterministic Turing Machine

\delta: Q \times \Gamma \rightarrow \gamma(Q \times \Gamma \times {L, R})
定理：任何non-deterministic Turing Machine等同於Deterministic Turing Machine
證明步驟如下：

  1. 初始tape 1包含輸入w的字串，tape 2跟tape 3先塞空字串
  2. 複製tape 1的內容到tape 2
  3. 使用tape 2在一條non-deterministic計算之下去模擬w的N個輸入，先查看tape 3下一個symbol的位置之前來決定讀寫頭如何移動，如果已經沒有符號在裡面了就進到步驟4，如果reject也進到步驟4
  4. 增加tape 3的次數，回到步驟2

推論1：一個language可以被non-deterministic Turing Machine給識別(recognizes)的話若且唯若稱這個language是Turing-recognizable
推論2：一個language可以被non-deterministic Turing Machine給決定(decides)的話若且唯若稱這個language是decidable

Enumerators

讓Turing Machine多一個可以列印的元件，language產生的所有字串都可以被enumerator給枚舉出來

定理：一個language可以被某些enumerator給枚舉language裡所有的字串若且唯若稱這個Turing Machine是Turing-recognizable
證明：

  1. 如果一個Enumerator E可以枚舉language A同時存在一個TM M可以recognizes這個A，M = 輸入w
    • 執行E，比較E產出來的字串跟w是不是相同
    • 如果w全部的排列組合都被E給輸出完就代表accept
  2. 如果Turing Machine M可以recognizes一個language A，同時也可以建構屬於A的enumerator
    存在S_{1},S_{2},…屬於\Sigma^{*}所有可能的字串，E = 無視所有輸入
    • 重複i = 1, 2, 3, …
    • 根據i的步驟執行M產出S_{1}, S_{2}, …, S_{i}
    • 如果任何計算都是accept的話，輸出相關的S_{i}

Scientia

我是Scientia，研究興趣包含Cryptology, Cryptographic Engineering, Security and Privacy, Computational Complexity, Quantum Cryptography, Cybersecurity, Hardware Security以及Anomaly Detection.

Related Posts

NP-Completeness
NP-Completeness

首先需要一個問題叫做布林公式(Boolean formula)會像：

    \[\phi = (\bar{x} \wedge y) \vee (x \wedge \bar{z})\]

裡面的每一個符號稱作variable，每一個variable可以給0或1的值就像在做.

Continue reading
時間複雜度
時間複雜度

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

Continue reading

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You Missed

資訊安全 防火牆

Palo Alto Firewall URL過濾 以及 Application Block Page

Palo Alto Firewall URL過濾 以及 Application Block Page
數學 數論

群

群
理論電腦科學 計算理論

NP-Completeness

NP-Completeness
異常檢測

異常檢測 問題分類

異常檢測 問題分類
異常檢測

異常檢測 方法評估

異常檢測 方法評估
異常檢測

異常檢測簡介 Anomaly Detection

異常檢測簡介 Anomaly Detection