ABC: Analysing boundaries of computation

ABC : Analysing Boundaries of Computation
part of the TASS Research Group
Department of Computer Science
NUI Maynooth, Ireland

Introduction
Members
Active Research Areas
Publications, Reports, Seminars
Teaching

nalysing oundaries of omputation
Group contact: Thomas J. Naughton
We are interested in unconventional models of computation and the resources used by their `computations', whether discrete or continuous, whether constant, finite, or from a level of infinity.
ABC is a subgroup of the Theoretical Aspects of Software Systems (TASS) research group. For an overview of TASS (including members, collaborators, and subgroups) see the TASS homepage.

Introduction

The study of computer science gives one a firm grasp, through mathematics, of both the theoretical and practical limits of computers, with applications ranging from the design of efficient algorithms, proving the correctness of programs, computer engineering and the Internet, through to artificial intelligence and virtual reality. The subject has an interesting history with pioneers such as Alan Turing (universal computation), Kurt Gödel (limits of computation), John von Neumann (stored-program architecture), Claude Shannon (information theory), and Stephen Cook (computational complexity); and more recently with Tom Head and Len Adleman (DNA computing) and Peter Shor (quantum computing).

The ABC group is concerned with exploring the boundaries of computation. In particular, it is concerned with non-standard models of computation, the (fractal) boundary between different levels of algorithmic complexity (with most interest on the boundary between P and NP), analysis of the limits of evolutionary computation and genetic algorithms, and the formulation of a more complete model of complexity (with respect to artificial intelligence and learning).

Members

Current members of ABC are

Active Research Areas

Continuous-space model of computation

Relationship between computational models and scientific theories

Computational analysis of unconventional models of computation

Optical computing and computational complexity

Relevant Publications, Reports, and Seminars

Journal papers

D. Woods and T.J. Naughton, "An optical model of computation," Theoretical Computer Science, vol. 334, no. 1-3, pp. 227-258, April 2005. (© Elsevier.)
Invited presentations
D. Woods, "Optical computing and computational complexity", (Invited.) UC'06 - Fifth International Conference on Unconventional Computation, York, UK 2006, (To appear).
D. Woods, "Computational complexity of an optical model of computation," International workshop on computations on the continuum, Lisbon, Portugal, 27-28 June, 2005. (Invited.)
D. Woods, T.J. Naughton, and J.P. Gibson, "Continuous-space model of computation," Spring Western Section Meeting of the American Mathematical Society, Meeting #987, San Francisco, California, 3-4 May 2003. (Invited.)
Book chapters and Springer LNCS
T. Neary and D. Woods, "P-completeness of cellular automaton Rule 110", ICALP 2006 - International Colloquium on Automata Languages and Programming, Venice, Italy. Springer Lecture Notes in Computer Science. Accepted. (Preliminary version availiable as BCRI Preprint 04/2006. See below.) (© Springer-Verlag.)
D. Woods, "Upper bounds on the computational power of an optical model of computation", ISAAC 2005 - The 16th Annual International Symposium on Algorithms and Computation, Sanya, Hainan, China, December 2005. Springer Lecture Notes in Computer Science vol. 3827, pp 777-788, 2005. (© Springer-Verlag.)
D. Woods and J.P. Gibson, "Lower bounds on the computational power of an optical model of computation," UC'05 - Fourth International Conference on Unconventional Computation, Sevilla, October 2005, Springer Lecture Notes in Computer Science vol. 3699, pp. 237-250, 2005. (© Springer-Verlag.)
D. Woods and J.P. Gibson, "Complexity of continuous space machine operations," CiE'05 - Computability in Europe 2005: New Computational Paradigms, Amsterdam, June 2005, S. B. Cooper, B. Löwe, and L. Torenvliet, Eds. Springer Lecture Notes in Computer Science vol. 3526, pp 540-551, 2005. (© Springer-Verlag.)
A. Delaney and T.J. Naughton, "Emulation of an unconventional model of computation in Java," in James F. Power and John T. Waldron, Eds., Recent Advances in Java Technology: Theory, Application, Implementation, chap. 1, pp. 1-9, Computer Science Press, Trinity College Dublin, Ireland, 2002. ISBN: 0-9544145-0-0
T.J. Naughton and D. Woods, "On the computational power of a continuous-space optical model of computation," Third International Conference on Machines, Computations, and Universality, Maurice Margenstern and Yurii Rogozhin, Eds., Lecture Notes in Computer Science vol. 2055, pp. 288-299, Chisinau, Moldova, May 2001. (© Springer-Verlag.)
Theses
D. Woods, "Computational complexity of an optical model of computation," Ph.D. Thesis, National University of Ireland, Maynooth, County Kildare, Ireland, 2005.
Conference papers
D. Woods, T.J. Naughton, and J.P. Gibson, "Continuous-space model of computation," Special Session on Beyond Classical Boundaries of Computability, Mark Burgin and Peter Wegner, Eds., Spring Western Section Meeting of the American Mathematical Society, Meeting #987, San Francisco, California, 3-4 May 2003. (Invited paper.) Reprinted in Abstracts of Papers Presented to the American Mathematical Society, vol. 24, no. 3, p. 484, September 2003.
A. Delaney, T.J. Naughton, and D. Woods, "Towards a minimal computational power operating system," British Colloquium for Theoretical Computer Science, no. 19, Leicester, UK, 7-9 April 2003.
A. Delaney and T.J. Naughton, "Emulation of an unconventional model of computation in Java," Principles and Practice of Programming in Java, James F. Power and John T. Waldron, Eds., pp. 1-6, Dublin, Ireland, June 2002.
T.J. Naughton, "Continuous-space model of computation is Turing universal," in Critical Technologies for the Future of Computing, Sunny Bains and Leo J. Irakliotis, Eds., Proceedings of SPIE vol. 4109, pp. 121-128, San Diego, California, August 2000. (© SPIE.)
T.J. Naughton, "A model of computation for Fourier optical processors," in Optics in Computing, Roger A. Lessard and Tigran Galstian, Eds., Proceedings of SPIE vol. 4089, pp. 24-34, Quebec, Canada, June 2000. (© SPIE.)
D. Woods and A. Treneman, "Simultaneous satisfaction of hard and soft timetable constraints for a university department using evolutionary timetabling", Proceedings of Artificial Intelligence & Cognitive Science 1999, Cork, Ireland, September 1999.
Technical reports
N. Murphy, D. Woods, and T.J. Naughton, "Stable sorting using special-purpose physical devices," BCRI Preprint 06/2006, May 2006, Boole Centre for Research in Informatics, University College Cork, Ireland.
T. Neary and D. Woods, "P-completeness of cellular automaton Rule 110", BCRI Preprint 04/2006, April 2006, Boole Centre for Research in Informatics, University College Cork, Ireland.
T. Neary and D. Woods, "A small fast universal Turing machine," Technical Report NUIM-CS-TR-2005-12, Department of Computer Science, National University of Ireland, Maynooth, 2005.
T. Neary and D. Woods, "Small fast universal Turing machines," Technical Report NUIM-CS-TR-2005-11, Department of Computer Science, National University of Ireland, Maynooth, 2005.
N. Murphy, D. Woods, and T.J. Naughton, "On the computational power of photosynthesis," Technical Report NUIM-CS-TR-2005-03, Department of Computer Science, National University of Ireland, Maynooth, April 2005.
T. Neary and D. Woods, "Simulating Turing machines using switching map systems," Technical Report NUIM-CS-TR-2003-11, Department of Computer Science, National University of Ireland, Maynooth, December 2003.
D. Woods and T.J. Naughton, "Analog recurrent neural network simulation and Theta(log₂ n) unordered search with an optically-inspired model of computation," Technical Report NUIM-CS-TR-2003-04, Department of Computer Science, National University of Ireland, Maynooth, March 2003.
D. Woods, T.J. Naughton and J.P. Gibson, "Analog recurrent neural network simulation, Theta(log₂ n) unordered search, and bitonic sort with an optically-inspired model of computation," Technical Report NUIM-CS-TR-2001-06, Department of Computer Science, National University of Ireland, Maynooth, October 2001. (This report is a preliminary version of NUIM-CS-TR-2003-04 above.)
T.J. Naughton and D. Woods, "On the computational power of a continuous-space optical model of computation," Technical Report NUIM-CS-TR-2001-01, Department of Computer Science, National University of Ireland, Maynooth, January 2001.
Seminars
D. Woods, "An optical model of computation", AMS Meeting, San Francisco, California, May 2003 and CS Departmental Seminar, NUIM, April 2003.
D. Woods, "Models of computation and scientific theories", NUIM Postgraduate Research Students Colloquium, March 2002.
D. Woods, "On the computational power of a continuous-space optical model of computation", conference presentation, MCU `01, May 2001.
J.P. Gibson, "The fractal-like nature of complexity boundaries", Formal Methods and Security Seminar Series, CS, NUIM, March 2001.
J.P. Gibson, "Computability, complexity, correctness, and common-sense", Department of Mathematics, NUIM, February 2001.
D. Woods, "Computing the uncomputable, an introduction", Departmental Seminar, CS, NUIM, January 2001.
J.P. Gibson, "Three interesting problems in computer science", Departmental Seminar, CS, NUIM, November 2000.
D. Woods, "Biomolecular computation, an introduction", Bio-med Computing and Engineering Reading Group, CS, NUIM, May 2000.
T.J. Naughton, "A Model of Computation for Fourier Optical Processors", Departmental Seminar, CS, NUIM, December 1999.
T.J. Naughton, "Church of the Millennium", Departmental Seminar, CS, NUIM, January 1999.

Teaching

The following relevant courses have recently been taught by ABC members.

CS605 - Mathematics and Theory of Computer Science (TN)
CS405 - Parallel Processing (JPG)
CS355 - Theory of Computation (TN)
CS370 - Computation and Complexity (TN)

TN (2002), TN (2001), TN (2000), TN (1999)
DW (2002)
JPG (2002)

URL: http://www.cs.nuim.ie/~tnaughton/abc
Last updated: May 2006
Contact: