[FOM] Status of Quantum Computing vis-a-vis Chomsky Hierarchy/Computing

Dennis E. Hamilton dennis.hamilton at acm.org
Wed Oct 16 20:28:20 EDT 2002

Just to complete the context, Rogers considers (at least up to 1967) that
*1-*5 are plausible and consistent with widely-held though informal notions
of algorithm.

Rogers reckons that *6-*8 and *10 are not plausible, but that *9 is.  He
provides justifications for his position on each of *6-*10 and also claims
that his view is substantiated in the formal characterization that he sets

-- orcmid

Dennis E. Hamilton
mailto:dennis.hamilton at acm.org
tel. +1-206-932-6970
cell +1-206-779-9430
     The Miser Project: http://miser-theory.info/
     AIIM DMware: http://DMware.info/

-----Original Message-----
From: fom-admin at cs.nyu.edu [mailto:fom-admin at cs.nyu.edu]On Behalf Of
Steve Stevenson
Sent: Wednesday, October 16, 2002 07:27
To: Duraid Madina
Cc: 'Steve Stevenson'; fom at cs.nyu.edu; jclayho at mail.clemson.edu
Subject: RE: [FOM] Status of Quantum Computing vis-a-vis Chomsky

[ ... ]

I had *3, *4, and *5 in mind in asking the question. *3 is suspect due
to entanglement and the measurement side effects. *4 is suspect due to
the "continuous methods or analogue devices". *5 is suspect due to "dice".

[ ... ] I would say *8 and *9 are suspect.

Best regards,

D. E. (Steve) Stevenson, Department of Computer Science, Clemson

FOM mailing list
FOM at cs.nyu.edu

More information about the FOM mailing list