Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!zaphod.mps.ohio-state.edu!casbah.acns.nwu.edu!ucsd!sdcc6!euler!sbloch
From: sbloch@euler.ucsd.edu (Steve Bloch)
Newsgroups: comp.theory
Subject: Re: Reverse Gear on a Turing Machine...
Message-ID: <19745@sdcc6.ucsd.edu>
Date: 25 May 91 00:48:37 GMT
References: <1991May13.175251.6537@cs.cornell.edu>
Sender: news@sdcc6.ucsd.edu
Organization: Mathematics @ UCSD
Lines: 29

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