Title: 單帶圖靈機的時空轉換（Time Versus Space on Single Tape Turing Machines）

Speaker: 夏盟佶 (中國科學院軟件研究所，計算機科學國家重點實驗室)

Time: 2020.12.9，星期三下午，1:30-2:30

Venue: 中科院軟件園區5號樓334房間，計算機科學國家重點實驗室報告廳

Abstract: 基于Kojiro Kobayashi 1985年的證明“單帶圖靈機o(n log n)時間內可以計算的語言都是正規語言”的方法，證明對于函數f(n)，單帶圖靈機的o(f log f)時間內可以計算的語言都可在 O(f) 空間內計算。受1977年JACM上關于多帶圖靈機一個相似結論激勵，進一步把結論加強到了：單帶圖靈機的O(f log f)時間內可以計算的語言都可在 O(f) 空間O(f log f)時間內計算。
Based on the methods in proving that all languages decided by single tape TMs in o(n log n) time are regular, by Kobayashi in 1985,  we prove for some functions f(n), all languages decided by single tape TMs in o(f log f) time can be decided in O(f) space. Inspired by a similar complexity result in JACM 1977, we strengthen the conclusion to that all languages decided by single tape TMs in o(f log f) time can be decided by in O(f) space and O(f log f) time.

Bio: 夏盟佶，中國科學院軟件研究所研究員, 博士生導師。