6 results for Arulanandham, J.J

Solving SAT with Bilateral Computing
Arulanandham, J.J; Calude, C.S; Dinneen, Michael (200212)
Report
The University of Auckland LibraryWe solve a simple instance of the SAT problem using a natural physical computing system based on fluid mechanics. The natural system functions in a way that avoids the combinatorial explosion which generally arises from the exponential number of assignments to be examined. The solution may be viewed as part of a more general type of natural computation called Bilateral Computing. The paper will also describe this new computing paradigm and will compare it with Reversible Computing. Our approach is informal: the emphasis is on motivation, ideas and implementation rather than a formal description.
View record details 
Implementing BeadSort with P systems
Arulanandham, J.J (200205)
Report
The University of Auckland LibraryIn this paper, we implement BeadSort, a natural sorting algorithm we introduced in [1], with the new, biochemically inspired P systems. We make use of a special type of P system – a tissue P system that computes by means of communication (using symport/antiport rules) only.
View record details 
A Fast Natural Algorithm for Searching
Arulanandham, J.J; Calude, C.S; Dinneen, Michael (200306)
Report
The University of Auckland LibraryIn this note we present two natural algorithms—one for sorting, and another for searching a sorted list of items. Both algorithms work in O(√N) time, N being the size of the list. A combination of these algorithms can search an unsorted list in O(√N) time, an impossibility for classical algorithms. The same complexity is achieved by Grover’s quantum search algorithm; in contrast to Grover’s algorithm which is probabilistic, our method is guaranteed correct. Two applications will conclude this note.
View record details 
Balance Machines: Computing = Balancing
Arulanandham, J.J; Calude, C.S; Dinneen, Michael (200310)
Report
The University of Auckland LibraryWe propose a natural computational model called a balance machine. The computational model consists of components that resemble ordinary physical balances, each with an intrinsic property to automatically balance the weights on their left, right pans. If we start with certain fixed weights (representing inputs) on some of the pans, then the balancelike components would vigorously try to balance themselves by filling the rest of the pans with suitable weights (representing the outputs). This balancing act can be viewed as a computation. We will show that the model allows us to construct those primitive (hardware) components that serve as the building blocks of a general purpose (universal) digital computer: logic gates, memory cells (flipflops), and transmission lines. One of the key features of the balance machine is its “bidirectional” operation: both a function and its (partial) inverse can be computed spontaneously using the same machine. Some practical applications of the model are discussed.
View record details 
BeadSort: A Natural Sorting Algorithm
Arulanandham, J.J; Calude, C.S; Dinneen, Michael (200201)
Report
The University of Auckland LibraryNature is not only a source of minerals and precious stones but is also a mine of algorithms. By observing and studying natural phenomena, computer algorithms can be extracted. In this note, a simple natural phenomenon is used to design a sorting algorithm for positive integers, called here BeadSort. The algorithm's run time complexity ranges from O(1) to O(S) (S is the sum of the input integers) depending on the user's perspective. Finally, three possible implementations are suggested.
View record details 
Balance Machines: A New Formalism for Computing
Arulanandham, J.J; Dinneen, Michael (200412)
Report
The University of Auckland LibraryThe Balance Machine is a newly proposed natural computational model that consists of components resembling physical balances. The model has only one operation, “balancing", which suffices in principle to perform universal computation. An interesting feature of the balance machine is its bidirectional operation: it can compute “forwards and backwards", i.e. both a function and its partial inverse can be computed spontaneously using the same machine. Also, the machine exhibits a different kind of parallelism – a “bilateral parallelism". The aim of this note is twofold: To introduce a formalism for computing with balance machines – a convenient notation for representing the mechanical model on paper, and to demonstrate its expressive power by solving two NP{complete problems, namely, Set Partition and Knapsack
View record details