🚀 go-pugleaf

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?

Because one stack can hold the contents of the tape to the left of the
pointer, and the other stack can hold the portion of the tape to the
right of the pointer. Thus, a TM is easy to simulate.

>Why is it important to know if there is at least one decision problem that is
>undecidable?

Importance depends on who you are. Many programmers life happily
without knowing about the unsolvability of the halting problem, but if
you have one specific problem that you know is undecidable, you can
often use this to prove the undecibability of other problems.

>Who cares if P=NP?  Or what is the significance of the question "Is P=NP"?

If P=NP then there exist efficient algorithms to solve problems, where
the best known current algorithms are so inefficient that it is
unrealistic to solve certain problems. There was/is a discussion (in
comp.theory or sci.math) about the consequence for "unbreakable"
codes. In essence, the point is that if P=NP it is impossible to make
a code that it takes exponential time to break.

	Torben Mogensen (torbenm@diku.dk)