Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!zaphod.mps.ohio-state.edu!ncar!midway!midway.uchicago.edu!stuart From: stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz) Newsgroups: comp.theory Subject: Re: Reverse Gear on a Turing Machine... Message-ID: Date: 28 May 91 17:03:15 GMT References: <1991May13.175251.6537@cs.cornell.edu> <19745@sdcc6.ucsd.edu> Sender: news@midway.uchicago.edu (NewsMistress) Organization: Dept. Computer Sci., University of Chicago Lines: 23 There's a very nice theorem by Charles Bennett that shows that every 1-1 recursive function can be computed by a TM whose transition function is invertable. Moreover, the total space involved in the simulation is quadratic, i.e., if the original machine runs in space s(n), the simulation runs in space s^2(n). Bennett's motivation for this work had to do with thermodynamics(!), specifically, do the laws of thermodynamics entail direct limits on computation? His result shows that they do not. Fenner used Bennett's theorem to prove the following, which is half of a complexity theoretic analog to Cantor-Bernstein/Myhill: If every polynomial time 1-degree consists of a single polynomial time isomorphism type, then P = PSPACE. Royer and I (using technology that doesn't depend on reversibility) established the converse. This appeared in FOCS: Every Polynomial-Time 1-Degree Collapses iff P = PSPACE, Fenner, Kurtz, Royer. Proc. 30th IEEE Symp. Foundation of Comp. Sci. (1989), p.624-629. Stu