home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2757 < prev    next >
Encoding:
Internet Message Format  |  1992-12-26  |  804 b 
  1. Path: sparky!uunet!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh
  2. From: markh@csd4.csd.uwm.edu (Mark)
  3. Newsgroups: comp.theory
  4. Subject: Re: 2 stack PDA and other questions
  5. Date: 26 Dec 1992 18:13:50 GMT
  6. Organization: Computing Services Division, University of Wisconsin - Milwaukee
  7. Lines: 10
  8. Distribution: inet
  9. Message-ID: <1hi7cuINN5hm@uwm.edu>
  10. References: <1992Dec13.162048.14632@miavx1.acs.muohio.edu>
  11. NNTP-Posting-Host: 129.89.7.4
  12.  
  13. In article <1992Dec13.162048.14632@miavx1.acs.muohio.edu> khmak@miavx1.acs.muohio.edu writes:
  14. >A few days ago someone posted a few questions that I was also curious about
  15. >knowing the answer to.  Here they are:
  16. >
  17. >
  18. >Why is a 2 stack PDA equivalent to a turing machine?
  19.  
  20. Given stacks A, and B:
  21. "Move left"  =  X = Pop(A); Push(B, X)
  22. "Move right" =  X = Pop(B); Push(A, X)
  23.