• 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:
    • Leiden Center for Natural Computing. A center that promotes research and education in Natural Computing: Molecular Computing, Evolutionary Algorithms and Neural Networks
    • Church-Turing Thesis at Stanford Encyclopedia of Philosophy, MathWorld, Wikipedia
    • Laboratory for Molecular Science at University of Southern California This lab is headed by Len Adleman whose work helped launch the new field of research, "DNA Computing". Original works of Adleman (and others) can be downloaded from here.
    • P Systems Web Page. All information pertaining to P Systems -- research publications, conferences, open problems, etc. can be found here.
    • Caltech's "Computing Beyond Silicon" Summer School (2002).
    • Billiard Ball Computer. A brief introduction to the Billiard Ball Model of computation accompanied by a Java applet.
    • Oxford Centre for Quantum Computation. Provides useful information and links to all material in the field of quantum computing and information processing.
    • Cambridge Centre for Quantum Computation. The Centre conducts theoretical research into all aspects of quantum information processing, and into the implications of the quantum theory of computation for physics itself.
    • Caltech Institute for Quantum Information. The Institute sponsors programs which encourage the growth and development of quantum information science.
    • Quantum Information and Information Physics at IBM Research Yorktown. Page is dedicated to Rolf Landauer (1927-1999) who is largely responsible form making the physics of information a serious subject of scientific study. The group's main work is in quantum information and computation theory and other aspects of the relation between physics and information processing.
    • Departmental Policy on Cheating