search

kkdai / blog2

for import data testing
0 stars 0 forks source link

moocs-coursera-automata-note5/ #18

Closed kkdai closed 3 years ago

kkdai commented 3 years ago

[Coursera][Automata] 自動機理論-Automata筆記-第五週: Turing Machines and Undecidability

http://www.evanlin.com/moocs-coursera-automata-note5/

kkdai commented 3 years ago

comment written by Dboy Liao, created at 25 Oct 15 15:38 UTC,

http://web.stanford.edu/cla...

這個 slides 不錯~

kkdai commented 3 years ago

comment written by Dboy Liao, created at 25 Oct 15 15:45 UTC,

剛看完 TM 就一直在想我要怎麼用 TM 數東西?
有什麼直覺 + 建構式的思考方式?
這份 slide 剛好示範了怎麼用 TM 數 0 跟 1 的個數~
基本上數東西的策略就是一個接一個消掉~
譬如說如果消掉一個 0 就接著消掉一個 1 ~
如果消到最後消光光就 accept ~
反之 reject ~
這樣就能用 TM 數東西~
配合 state 就可以數多個東西~
甚至像是多少 0 就配 2 倍長的 1 等等語言都可以用這種想法建構出來~

呼....總算對 TM 有一點點兒感覺了!