係乜嘢可以作為概率同非決定性圖靈機器嘅基礎? 根據上個問題,寫一個包含答案嘅上下文. 可以係一句到廿句 背景:
一部決定性嘅圖靈機器係最基本嘅圖靈機器,佢利用一套固定嘅規則嚟決定佢未來嘅動作. 一部概率式嘅圖靈機器,就係一台有額外隨機位嘅定律式圖靈機器. 作出概率性決定嘅能力 經常幫助算法更有效咁解決問題 用隨機位數嘅算法叫做隨機算法 非決定性嘅圖靈機器 (Non-deterministic Turing machine) 係一種具有非決定性嘅特點嘅決定性圖靈機器,佢可以使圖靈機器喺一個特定狀態下有多個可能嘅未來動作. 一種睇非決定論嘅方法係 圖靈機器喺每一步分成好多可能嘅計算路徑 如果佢喺任何一個分支解決咗問題,就已經解決問題. 顯然,呢個模型唔係一個物理上可以實現嘅模型 而係一個理論上好有趣嘅抽象機器 呢個機器可以產生一個好有趣嘅複雜級別 有關例子,請見非決定性算法.