The field of computational complexity theory--which chiefly aims to quantify the difficulty encountered when performing calculations--is, in the case of conventional computers, correctly practised and well understood (some important and fundamental open questions notwithstanding); however, such understanding is, we argue, lacking when unconventional paradigms are considered. As an illustration, we present here an analogue computer that performs the task of natural-number factorization using only polynomial time and space; the system's true, exponential complexity, which arises from requirements concerning precision, is overlooked by a traditional, `time-and-space' approach to complexity theory. Hence, we formulate the thesis that unconventional computers warrant unconventional complexity analysis; the crucial omission from traditional analysis, we suggest, is consideration of relevant resources, these being not only time and space, but also precision, energy, etc. In the presence of this multitude of resources, however, the task of comparing computers' efficiency (formerly a case merely of comparing time complexity) becomes difficult. We resolve this by introducing a notion of overall complexity, though this transpires to be incompatible with an unrestricted formulation of resource; accordingly, we define normality of resource, and stipulate that considered resources be normal, so as to rectify certain undesirable complexity behaviour. Our concept of overall complexity induces corresponding complexity classes, and we prove theorems concerning, for example, the inclusions therebetween. Our notions of resource, overall complexity, normality, etc. form a model-independent framework of computational complexity theory, which allows: insightful complexity analysis of unconventional computers; comparison of large, model-heterogeneous sets of computers, and correspondingly improved bounds upon the complexity of problems; assessment of novel, unconventional systems against existing, Turing-machine benchmarks; increased confidence in the difficulty of problems; etc. We apply notions of the framework to existing disputes in the literature, and consider in the context of the framework various fundamental questions concerning the nature of computation.

This thesis presents an investigation into developing musical systems with an Unconventional Computing substrate. Computer musicians have found it difficult to access the field of Unconventional Computing, which is likely due to its resource-intensive and complex nature. However, ongoing research is establishing the myxomycete Physarum polycephalum as a universally-accessible and versatile biological computing substrate. As such, the organism is a potential gateway for computer musicians to begin experimenting with aspects of Unconventional Computing. Physarum polycephalum, in its vegetative plasmodium form, is an amorphous unicellular organism that can respond with natural parallelism to the environmental conditions that surround it. This thesis explores the challenges and opportunities related to developing musical systems with Physarum polycephalum. As this area of inquiry is in its infancy, the research took inspiration from a common approach in Unconventional Computing: a journey of exploration and discovery. This journey consisted of a selection of waypoints that provided direction while allowing the research to explore applications of Physarum polycephalum in order to establish how it may be useful in Computer Music. These waypoints guided the research from adapting established prototypes for musical application to developing purpose-made musical demonstrators for use outside of the laboratory. Thus, the thesis reports on a series of Computer Music systems that explore one or more features of Physarum polycephalum's behaviour and physiology. First, the text presents an approach to algorithmic composition that exploits the organism's ability to form and reconfigure graph-like structures. Next, the thesis reports on systems that harness the plasmodium's electrical potential oscillations for sound synthesis and compositional tools. Finally, the thesis presents musical devices that encompass living plasmodium as electrical components. Where applicable, the thesis includes artefacts from demonstrations of these systems, some of which were developed in collaboration with a composer. The findings from this journey demonstrate that Physarum polycephalum is an appropriate substrate for computer musicians wanting to explore Unconventional Computing approaches creatively. Although Physarum polycephalum is relatively robust as a biological substrate, several obstacles arose during this project. This research addressed such obstacles by reviewing and selecting approaches that maintained the organism's accessibility to computer musicians. As a result, the work suggests methods for developing systems with the organism that are practical for the average music technologist and also beneficial to the wider group of scientists investigating Physarum polycephalum for other purposes.

Yes / Computational theory and practice generally focus on single-paradigm systems, but relatively little is known about how best to combine components based on radically different approaches (e.g. silicon chips and wetware) into a single coherent system. In particular, while testing strategies for single-technology artefacts are generally well developed, it is unclear at present how to perform integration testing on heterotic systems: can we develop a test-set generation strategy for checking whether specified behaviours emerge (and unwanted behaviours do not) when components based on radically different technologies are combined within a single system? In this paper, we describe an approach to modelling multi-technology heterotic systems using a general-purpose formal specification strategy based on Eilenberg's X-machine model of computation. We show how this approach can be used to represent disparate technologies within a single framework, and propose a strategy for using these formal models for automatic heterotic test-set generation. We illustrate our approach by showing how to derive a test set for a heterotic system combining an X-machine-based device with a cell-based P system (membrane system).

Les modèles géométriques de calcul permettent d’effectuer des calculs à l’aide de primitives géométriques. Parmi eux, le modèle des machines à signaux se distingue par sa simplicité, ainsi que par sa puissance à réaliser efficacement de nombreux calculs. Nous nous proposons ici d’illustrer et de démontrer cette aptitude, en particulier dans le cas de processus massivement parallèles. Nous montrons d’abord à travers l’étude de fractales que les machines à signaux sont capables d’une utilisation massive et parallèle de l’espace. Une méthode de programmation géométrique modulaire est ensuite proposée pour construire des machines à partir de composants géométriques de base les modules munis de certaines fonctionnalités. Cette méthode est particulièrement adaptée pour la conception de calculs géométriques parallèles. Enfin, l’application de cette méthode et l’utilisation de certaines des structures fractales résultent en une résolution géométrique de problèmes difficiles comme les problèmes de satisfaisabilité booléenne SAT et Q-SAT. Ceux-ci, ainsi que plusieurs de leurs variantes, sont résolus par machines à signaux avec une complexité en temps intrinsèque au modèle, appelée profondeur de collisions, qui est polynomiale, illustrant ainsi l’efficacité et le pouvoir de calcul parallèle des machines a signaux. / Geometrical models of computation allow to compute by using geometrical elementary operations. Among them, the signal machines model distinguishes itself by its simplicity, along with its power to realize efficiently various computations. We propose here an illustration and a study of this ability, especially in the case of massively parallel processes. We show first, through a study of fractals, that signal machines are able to make a massive and parallel use of space. Then, a framework of geometrical modular programmation is proposed for designing machines from basic geometrical components —called modules— supplied with given functionnalities. This method fits particulary with the conception of geometrical parallel computations. Finally, the joint use of this method and of fractal structures provides a geometrical resolution of difficult problems such as the boolean satisfiability problems SAT and Q-SAT. These ones, as well as several variants, are solved by signal machines with a model-specific time complexity, called collisions depth, which is polynomial, illustrating thus the efficiency and the parallel computational abilities of signal machines.