- 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 billiard-ball 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), Springer-Verlag, London, 2000.
- M. Brooks (ed.). Quantum Computing and Communications,
Springer-Verlag, Berlin, 1999.
- D. Bouwmeester, A. Ekert, A. Zeilinger (eds.)
The Physics of Quantum Information,
Springer-Verlag, 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,
Springer-Verlag, Heidelberg, 2001.
- C. S. Calude, J. L. Casti (eds.). Unconventional Models of
Computation, Complexity, Vol. 4, 1, (1998), 13-42. (special issue)
- C. S. Calude, J. Casti, M. Dinneen (eds.). Unconventional Models
of Computation, Springer-Verlag, Singapore, 1998.
- L.
A. Condon, G. Rozenberg (eds.).
DNA Computing.
6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, The
Netherlands,
June 13-17, 2000, Revised Papers, Springer-Verlag, Berlin, 2001.
- J. Gruska. Quantum Computing, McGraw-Hill, 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,
Addison-Wesley, 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,
Springer-Verlag, New York, 1997.
- Gh. Paun, G. Rozenberg, A. Salomaa. DNA Computing.
New Computing Paradigms, Springer-Verlag, 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,
Springer-Verlag, Heidelberg, 2000.
- Alex Morgan, an ex-student 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: