主題
Search

迴圈標籤系統


一種 標籤系統,其中 n 個標籤規則(每個規則都具有特殊形式)的列表按順序應用於系統,然後從第一個規則重新開始。在迴圈標籤系統中,每組標籤規則都具有特殊的結構:當且僅當當前模式的第一個元素為 1 時,才附加一個模式;並且無論第一個元素是 0 還是 1,第一個元素都會被刪除。

CyclicTagSystem

例如,考慮一個由白色和黑色單元格組成的狀態,分別標記為 0 和 1,以及迴圈標籤系統 {(1,...)->(...,1,1),(0,...)->(...)}{(1,...)->(...,1,0),(0,...)->(...)},初始狀態為 (1),如上圖所示。根據要求,此係統始終刪除第一個元素,並且當且僅當第一個單元格為黑色時才附加特定模式。

1. 在第一步中,最左邊的元素是 1,因此應用第一個規則得到 (1,1),因為附加了 (1,1),然後刪除了初始的 (1)

2. 應用第二個規則在末尾新增 (1,0) 並刪除第一個元素,得到 (1,1,0)

3. 再次應用第一個規則在末尾新增 (1,1) 並且(像往常一樣)刪除第一個元素,得到 (1,0,1,1)

4. 再次應用第二個規則得到 (0,1,1,1,0),依此類推 (Wolfram 2002, p. 95)。

可以構建一個迴圈標籤系統來模擬任何 圖靈機,因此通用的迴圈標籤系統是可能的 (Wolfram 2002, p. 678)。


另請參閱

字串重寫系統, 替換系統, 標籤系統

相關 Wolfram 站點

http://atlas.wolfram.com/06/03/

此條目部分內容由 Todd Rowland 貢獻

使用 探索

參考文獻

Wolfram, S. 一種新的科學。 Champaign, IL: Wolfram Media, pp. 95-96 和 895, 2002.

參考

迴圈標籤系統

引用為

Rowland, ToddWeisstein, Eric W. "迴圈標籤系統。" 來自 網路資源。 https://mathworld.tw/CyclicTagSystem.html

主題分類