[12-09] SKLCS seminar on “单带图灵机的时空转换（Time Versus Space on Single Tape Turing Machines）”

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: 夏盟佶，中国科学院软件研究所研究员, 博士生导师。