Is DTIME(n) closed under concat? star? of course not but...

Computational Complexity 2018-04-16

(STOC 2018 will offer child care for the first time. I was emailed the following and asked to pass it on: We are pleased to announce that we will provide pooled, subsidized child care at STOC 2018. The cost will be $40 per day per child for regular conference attendees, and $20 per day per child for students. For more detailed information, including how to register for STOC 2018 childcare, see http://acm-stoc.org/stoc2018/childcare.html Ilias Diakonikolas and David Kempe (local arrangements chairs) I tell my class that poly time is nice mathematically since its closed under lots of operations including concat and *.  That is: L1 , L2  ∈ P  implies L1 L2 ∈ P. unlike DTIME(n) which, as you can see, is NOT closed under concat! After all, the proof that P is closed under concat uses that if p(n) is a poly then np(n) is a poly which does not hold for linear time. If p(n) is O(n) then np(n) is NOT necc O(n). But--- thats not a proof that DTIME(n) is not closed under concat! Thats just the observation that the argument for P being closed under concat does not extend to DTIME(n). Perhaps some other argument does. I do not believe that. I believe there exists L1 , L2  ∈ DTIME(n) such that  L1 L2 is not in DTIME(n). I have not been able to prove this. In fact, the question I pose is not well defined since I need to specify a machine model. I pose the following question which may well be known - if so then please leave a comment: Find a reasonable machine model (RAM? k-tape TM?) such that DTIME(n) on that model is NOT closed under concat.  (Prob use DTIME(O(n))). Similar for * These are likely hard questions since if L is in DTIME(n) then L* is in NTIME(n), (similar for concat), so I would be separating DTIME(n) from NTIME(n), which HAS been done, but not with nice naturaly problems of the type that I seek.