 Title: Unconventional Models of Computation
 Credits: 2 Points
 Lecturer: Joshua Arulanandham, room 576, ext 87595,
hi_josh@hotmail.com
 Lecturer: Professor Cristian S. Calude, room 575, ext 85751,
cristian@cs.auckland.ac.nz
 Taught: First semester 2004, three lectures a week.

Timetable: Monday 9.00  10.00 am; Thursday 8.00  10.00 am; Computer Science
Seminar Room
 Short Description:
The conventional trend of computation is approaching a critical
phase and new technologies are required to provide significant further
progress. The paper will focus on the following new categories of unconventional
models: natural algorithms,
biologically inspired computing, reversible models
of
computation and quantum computation. A key objective will be the search for efficient solutions for
problems that are difficult or impossible to solve using classical (Turing
or equivalent) models.
 Topics:
 A short guide to literature
 Why unconventional models of computation?
 Fundamental mathematical constraints on computation
 Natural algorithms
 DNA computation
 P systems
 Fundamental physical constraints on computation
 The billiardball model of computation
 Quantum computation
 Relativistic computation
 Cellular automata
 Potential future computing technologies
 Implications for the mind theories
 Textbook:
 C.S. Calude, G. Paun. Computing with Cells and Atoms, Taylor and
Francis Publishers, London, 2001.

Texts recommended:
 I. Antoniou, C.S. Calude, M.J. Dinneen (eds.).
Unconventional Models
of Computation (UMC'2K), SpringerVerlag, London, 2000.
 M. Brooks (ed.). Quantum Computing and Communications,
SpringerVerlag, Berlin, 1999.
 D. Bouwmeester, A. Ekert, A. Zeilinger (eds.)
The Physics of Quantum Information,
SpringerVerlag, Berlin, 2000.
 C. S. Calude, Gh. Paun, G. Rozenberg, A. Salomaa (eds.).
Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View,
Lect. Notes Comput. Sci. 2235,
SpringerVerlag, Heidelberg, 2001.
 C. S. Calude, J. L. Casti (eds.). Unconventional Models of
Computation, Complexity, Vol. 4, 1, (1998), 1342. (special issue)
 C. S. Calude, J. Casti, M. Dinneen (eds.). Unconventional Models
of Computation, SpringerVerlag, Singapore, 1998.
 L.
A. Condon, G. Rozenberg (eds.).
DNA Computing.
6th International Workshop on DNABased Computers, DNA 2000, Leiden, The
Netherlands,
June 1317, 2000, Revised Papers, SpringerVerlag, Berlin, 2001.
 J. Gruska. Quantum Computing, McGrawHill, London, 1999.
 J. G. Hey (ed.). Feynman and Computation. Exploring the
Limits of Computers, Perseus
Books, Reading, Massachusetts, 1999.
 J. G. Hey and R. W.
Allen, (eds.). Feynman Lectures on Computation,
AddisonWesley, Reading, Massachusetts, 1996.
 T. Hida, K. Saito (eds.). Quantum Information Theory II,
World Scientific, Singapore, 2000.
 R. J. Lipton, E. B. Baum (eds.). DNA Based
Computers, Proc.
of a DIMACS Workshop, Princeton, 1995, Amer. Math. Soc., 1996.
 R. Lupacchini, G. Tamburrini (eds.). Grounding Effective Processes in Empirical
Laws, Reflections of the Notion of Algorithm, Bulzoni Editore, Bologna, 1999.
 C. P. Williams, S. H. Clearwater. Explorations in Quantum Computing,
SpringerVerlag, New York, 1997.
 Gh. Paun, G. Rozenberg, A. Salomaa. DNA Computing.
New Computing Paradigms, SpringerVerlag, Berlin, 1998.
 T. Siegfried. The Bit and the Pendulum, John Wiley, New York, 2000.
 C. P. Williams, S. H. Clearwater. Ultimate Zero and One: Computing at the
Quantum Frontier,
SpringerVerlag, Heidelberg, 2000.
 Alex Morgan, an exstudent in the class, has an
annotated list of websites related to Quantum Computation
 2002 Slides
 2004 Slides1,
Slides2,
Slides3,
Slides4,
Slides5,
Slides6
 Assessment: Assignments: 60% (assignments 25%, project 35%), Exam: 40%
 For queries or related matters send us an
email.
 Useful sites: