Newsgroups: comp.theory
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!batcomputer!cornell!wayner
From: wayner@CS.Cornell.EDU (Peter Wayner)
Subject: Reverse Gear on a Turing Machine...
Message-ID: <1991May13.175251.6537@cs.cornell.edu>
Sender: news@cs.cornell.edu (USENET news user)
Nntp-Posting-Host: kama.cs.cornell.edu
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Date: Mon, 13 May 1991 17:52:51 GMT
Lines: 18

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