6 results for Arulanandham, J.J

  • Solving SAT with Bilateral Computing

    Arulanandham, J.J; Calude, C.S; Dinneen, Michael (2002-12)

    Report
    The University of Auckland Library

    We 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 Bead--Sort with P systems

    Arulanandham, J.J (2002-05)

    Report
    The University of Auckland Library

    In this paper, we implement Bead-Sort, 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 (2003-06)

    Report
    The University of Auckland Library

    In 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 (2003-10)

    Report
    The University of Auckland Library

    We 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 balance-like 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 (flip-flops), 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
  • Bead--Sort: A Natural Sorting Algorithm

    Arulanandham, J.J; Calude, C.S; Dinneen, Michael (2002-01)

    Report
    The University of Auckland Library

    Nature 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 Bead-Sort. 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 (2004-12)

    Report
    The University of Auckland Library

    The 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 two-fold: 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