Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ncar!gatech!merlin!samir
From: samir@merlin.gatech.edu (Samir Ranjan Das)
Newsgroups: comp.theory
Subject: Re: Reverse Gear on a Turing Machine...
Message-ID: <1456@mephisto.edu>
Date: 27 May 91 19:15:36 GMT
References: <1991May13.175251.6537@cs.cornell.edu> <19745@sdcc6.ucsd.edu>
Sender: news@gatech.edu
Organization: Georgia Institute of Technology
Lines: 46

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
________________________________________________________________