wayner@CS.Cornell.EDU (Peter Wayner) (05/14/91)
Here is an interesting question: Has anyone ever run across any proof or discussion or theoretical construct that hinged on a turing machine running in reverse? I.E. start with a blank tape in an end state and non-determanistically inverting the state change function until the starting state was reached? If the state change function said write a symbol, the reverse would read a symbol and vice versa. Just wondering? -Peter -- Peter Wayner Department of Computer Science Cornell Univ. Ithaca, NY 14850 EMail:wayner@cs.cornell.edu Office: 607-255-9202 or 255-1008 Home: 116 Oak Ave, Ithaca, NY 14850 Phone: 607-277-6678
sbloch@euler.ucsd.edu (Steve Bloch) (05/25/91)
wayner@CS.Cornell.EDU (Peter Wayner) writes: >Has anyone ever run across any proof or discussion or theoretical >construct that hinged on a turing machine running in reverse? I.E. >start with a blank tape in an end state and non-determanistically >inverting the state change function until the starting state was >reached? Somebody posted to sci.logic a few months ago asking about things computable by Turing machines whose next-step function was invertible. I don't think there was much response, but I was reminded of Christos Papadimitriou's complexity class BP, which has to do with solving search problems in which for every point in the search space there are at most two adjacent points (one of which you presumably just came from, so the other must be where you're going next). For example, the missionaries-and-cannibals problem is like this except for four con- figurations. * * / \ / \ *---* *---*---*---*---*---*---*---* *---* (if I remember right) \ / \ / * * This might or might not be pertinent to Peter's question. -- "The above opinions are my own -- but that's just MY opinion." Stephen Bloch sbloch@math.ucsd.edu
samir@merlin.gatech.edu (Samir Ranjan Das) (05/28/91)
wayner@CS.Cornell.EDU (Peter Wayner) writes: >Has anyone ever run across any proof or discussion or theoretical >construct that hinged on a turing machine running in reverse? I.E. >start with a blank tape in an end state and non-determanistically >inverting the state change function until the starting state was >reached? sbloch@math.ucsd.edu (Steve Bloch) writes in response: >Somebody posted to sci.logic a few months ago asking about things >computable by Turing machines whose next-step function was invertible. >I don't think there was much response, but I was reminded of Christos >Papadimitriou's complexity class BP, which has to do with solving >search problems in which for every point in the search space there >are at most two adjacent points (one of which you presumably just came >from, so the other must be where you're going next). For example, the >missionaries-and-cannibals problem is like this except for four con- >figurations. C.H. Bennet of IBM has done some work on logical reversibilty of computation in the context of thermodynamic cost of computation. One of his latest work on reversible Turing Machines appears in SIAM J. Computing, Aug 1989 ("Time and Space Trade-Offs for Reversible Computation"). Interested readers can cross-reference from this paper to his other work in this context. Bennet's work considers only deterministic machines. There is a work by Lewis and Papadimitriou's in Theor. Comp. Sc. (1982) ("Symmetric Space-Bounded Computaion") that considers non-determinism. This work analyzes computational power of symmetric Turing Machines (loosely, machines having invertible state-transition functions) in relation to that of their determistic and nondeterminstic counterparts. However, the authors here do not consider running the machine in reverse from end to start and study its implications, as Bennet does. Samir ---------------------------------------------------------------- SAMIR RANJAN DAS PhD student and Graduate Research Assistant College of Computing Georgia Institute of Technology, Atlanta, Georgia, 30332-0280 uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!cc!samir Internet: samir@cc.gatech.edu Office: (404) 894-3982 Home: (404) 607-7147 ________________________________________________________________
stuart@cookie.cs.uchicago.edu (Stuart A. Kurtz) (05/29/91)
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