馬爾可夫算法
編輯在理論計算機科學中,馬爾可夫算法是一種字符串重寫系統,它使用類似語法的規則對符號字符串進行操作。 馬爾可夫算法已被證明是圖靈完備的,這意味著它們適合作為通用計算模型,可以用簡單的符號表示任何數學表達式。 馬爾可夫算法以蘇聯數學家小安德烈·馬爾可夫的名字命名。
Refal 是一種基于馬爾可夫算法的編程語言。
描述
編輯普通算法是口頭的,也就是說,旨在應用于不同字母表的字符串。
任何普通算法的定義都由兩部分組成:算法字母的定義(算法將應用于這些字母符號的字符串),以及其方案的定義。 普通算法的方案是一組有限有序的所謂替代公式,每個替代公式都可以是簡單的或最終的。 簡單替換公式由 L → D {\displaystyle L\to D} 形式的字符串表示,其中 L {\displaystyle L} 和 D {\displaystyle D} 是算法字母表中的兩個任意字符串 (分別稱為公式的左右兩邊代入)。 類似地,最終替換公式由 L → ? D {\displaystyle L\to \cdot D} 形式的字符串表示,其中 L {\displaystyle L} 和 D {\displaystyle D} 是兩個任意字符串 在算法的字母表中。 這假設輔助字符 → {\displaystyle \to } 和 → ? {\displaystyle \to \cdot } 不屬于算法的字母表(否則另外兩個字符執行它們作為分隔符的角色 應選擇不在算法字母表中的左側和右側)。
將普通算法應用于該算法字母表中的任意字符串 V {\displaystyle V} 的過程是一個離散的基本步驟序列,包括以下內容。 讓我們假設 V ′ {\displaystyle V'} 是在算法的前一步中獲得的單詞(如果當前步驟是xxx步,則為原始單詞 V {\displaystyle V} )。 如果替換公式中沒有包含在 V ′ {\displaystyle V'} 中的左側,則算法終止,其工作結果被認為是字符串 V ′ {\ 顯示樣式 V'} 。 否則,選擇左邊包含在 V ′ {\displaystyle V'} 中的xxx個替換公式。 如果替換公式的形式為 L → ? D {\displaystyle L\to \cdot D} ,那么在字符串 V ′ {\displaystyle V'} 的所有可能表示中,形式為 R L S {\displaystyle RLS}(其中 R {\displaystyle R} 和 S {\displaystyle S} 是任意字符串)選擇具有最短 R {\displaystyle R} 的字符串。 然后算法終止,其工作結果被認為是 R D S {\displaystyle RDS} 。 然而,如果這個替換公式的形式為 L → D {\displaystyle L\to D} ,那么在字符串 V ′ {\displaystyle V'} 的所有可能表示中,形式為 R L S {\displaystyle RLS} 最短的 R {\displaystyle R} 被選擇,之后字符串 R D S {\displaystyle RDS} 被認為是當前步驟的結果,在下一步進一步處理 步。
任何普通算法都等同于某種圖靈機,反之亦然——任何圖靈機都等同于某種普通算法。 Church-Turing 論文的一個版本是關于正常算法制定的,稱為規范化原則。
普通算法已被證明是構建構造性數學的許多部分的便捷手段。 此外,在普通算法的定義中固有的是一些在旨在處理符號信息的編程語言中使用的想法——例如,在 Refal 中。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/198239/