[問題] 單紙帶圖靈機與 o(n log n)

[suhorng ( )]

課本上有一題是說：任何可以被單紙帶圖靈機在 o(n log n) 時間內 recognize

的語言皆為 regular，但是沒有任何提示，實在想不到該如何下手。

請問能不能提示一下？

在網路上搜尋也沒有找到資料，除了找到別人的 homework ...:

http://www.cs.au.dk/~arnsfelt/CT08/homework/homework1.pdf

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.144.99
※ 編輯: suhorng         來自: 59.115.144.99        (11/08 23:28)
推 hcsoso:This theorem is proved by Kobayashi, which is not an
→ hcsoso:easy result. This may be helpful to you:
→ hcsoso:http://arxiv.org/abs/cs/0310046
推 Favonia:某本書收集了很多很難的問題... xD
→ suhorng:感謝一樓:) 用至這個當關鍵字搜尋到神奇的東西:
→ suhorng:       http://cc-li.blog.ntu.edu.tw/files/2011/01/
→ suhorng:       2010final_sol.pdf
→ suhorng:裡面 Problem 5 是這題並有解答...
推 Hseuler:老師出這題當期末考的時候全班沒人做出來