[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: quantum Computing

-----BEGIN PGP SIGNED MESSAGE-----

    Date: Wed, 18 May 94 13:03:43 CDT
    From: [email protected] (Mike McNally)
    
    An NFA has no tape . . .

Mine does :-)

It's a matter of definition, I suppose.  Hopcroft and Ullman describe
an NFA as having a tape.

On the other hand, they also descript the NP Completeness in terms of
an NTM, so I'll concede your point.

			Rick

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLdpbIRaZNKPPNj41AQHG+gQAtYMYanQzNIYeWV8DlIr+LAT8Lu7UNZWD
DzZMa30vlliUU9twWZW23fiQltWKGx0GG73IG3egLJ01Qeo1t7aN6Dl20+Jm2CIQ
xDxOrQc+I+rakSW4/MmC5PgfoXazKTtF3X+BaRXdkfZqvH0Lt9hvzaEJ0nA43iG9
YIpXYDesqcc=
=/Plo
-----END PGP SIGNATURE-----