Re: 2 stack PDA and other questions

Article View: comp.theory

Article #1685

#1685

From: Mark
Date: Sat, 26 Dec 1992 18:13

10 lines
826 bytes

In article <1992Dec13.162048.14632@miavx1.acs.muohio.edu> khmak@miavx1.acs.muohio.edu writes:
>A few days ago someone posted a few questions that I was also curious about
>knowing the answer to.  Here they are:
>
>
>Why is a 2 stack PDA equivalent to a turing machine?

Given stacks A, and B:
"Move left"  =  X = Pop(A); Push(B, X)
"Move right" =  X = Pop(B); Push(A, X)

Technical Details

Message-ID: <1hi7cuINN5hm@uwm.edu>

Path: arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh

References: <1992Dec13.162048.14632@miavx1.acs.muohio.edu>

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!sparky!uunet!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory
Subject: Re: 2 stack PDA and other questions
Date: 26 Dec 1992 18:13:50 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Lines: 10
Distribution: inet
Message-ID: <1hi7cuINN5hm@uwm.edu>
References: <1992Dec13.162048.14632@miavx1.acs.muohio.edu>
NNTP-Posting-Host: 129.89.7.4

Reply to Parent Message