# 2020.10.22 Meeting --- ### 本周討論這篇論文 Irina Kostitsyna, Cai Wood, Damien Woods Turning machines DNA26: The 26th International Conference on DNA Computing and Molecular Programming. 2020.  #### 論文重點 1. 使用Nubot的分子系統 2. 起始狀態(configuration)是一條直線鏈(且每個node皆為同一方向) 3. 規則：利用node上的state值，判斷如何旋轉(規則簡單) 4. 旋轉：每個node，State為正的情況下，轉一次State就減1，直到State = 0 5. 證明：在這樣的條件下，旋轉有何限制 6. 有兩種Blocking 會發生：permanent or temporary Blocking 7. 可以利用Zig-Zag的方式長成任意圖形 #### 討論 1. 本篇論文的概念，介於Amoebot和Nubot之間 (a) 如Amoebot般固定Monomers數量 (環境中的Nubot數量通常很多) (b) 如Nubot般的旋轉功能(Amoebot 沒法旋轉) (c ) 這篇的動機提到，在分子的世界設計Robot的概念 2. 對Nubot系統來說，這篇多了限制 (a) 起始條件固定 (b) 只有旋轉的Rule 3. 此系統用的Zig-Zag方式橫向foding後轉化成目標圖形， 但沒法處理直向彎曲的圖形 4. 這篇的起始條件為一條固定位置的直線鏈，對於貢獻似乎不夠，但是這篇論文最主要的貢獻在於即使是這麼簡單的規則，在旋轉的問題上也會有很多特性可以討論，其中一個證明說明了在5/6圈選轉是不可行(細節請參考論文證明) 5. 這篇有提到Parrallell的概念，雖然方法看起來不像，但是可以假設不太可能同時發生，每個轉動都有1/k的機率發生，其時間複雜的定義跟Nubot是一樣的 #### 延伸討論 * 對於Shape Formation 1. 建立特定Shape Formation的方法 a. 定義在State上 (例如這篇Turning Machine) b. 定義在Rule上(大部分分子系統的方法) 2. 定義在State上，比較不合理，因為在分子的世界不容易精準設計剛剛好的State狀態 3. 本篇論文的State是屬於不對稱 4. 如果要更廣義解決此類問題，State可以假定任意起始狀態，State是對稱(Symmetric) 5. 為何要導入Leader，因為各分子在Shape Transform的過程中是觀察不到global狀態，不知道圖形何時轉完，可以由Leader 來負責確認 * 在分子系統的容錯 1. Nubot因為還不是現實中可實現的模型，所以目前沒有討論容錯的問題 2. 因為aTAM已經可以在現實中實現，所以現實中會遇到很多的錯誤發生 3. 從一開始的10%, 1%, 0.1%，到最新的方法0.01%，已經有諸多這類的設計 4. 對Turning Machine系統來說，是不允許有錯誤發生(因為state狀態決定最後的shape) * 方向性問題 1. 因為本篇論文的方法(由State的正負號決定轉動的次數)，所以方向性是不可逆的 2. 因此一旦形成了Blocking ，就無法打開 3. 可否從複雜(初始狀態)捲曲的線，展成一條直線 4. 遇到Blocking的時候是否有辦法打開(一定的機率) * 補充討論 * 戴子宜解Structee population protocol 的問題，原本是要解ring的leader election 問題log(n)，但光是更新的方向就需要比較多的時間，所以她目前用一個log(n)的方法來解決方向性的問題 * 方向性的問題沒有在學平的論文上遇到的原因是因為，學平的論文是從隨機的狀態開始，為了達成self-stability，他就花了很多時間，所以反而方向的問題不會是拖慢的原因 ###### tags: `Molecular Computing`, `1-1 Meeting`