---
# System prepended metadata

title: 2020.10.22 Meeting
tags: [Molecular Computing, 1-1 Meeting]

---

# 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`