Tag: Natural Computing

Stateless multicounter 5′ → 3′ Watson–Crick automata: the deterministic case

Abstract  We consider stateless counter machines which mix the features of one-head counter machines and special two-head Watson–Crick
automata (WK-automata). These biologically motivated machines have heads that read the input starting fr…

Abstract  

We consider stateless counter machines which mix the features of one-head counter machines and special two-head Watson–Crick
automata (WK-automata). These biologically motivated machines have heads that read the input starting from the two extremes.
The reading process is finished when the heads meet. The machine is realtime or non-realtime depending on whether the heads are required to advance at each move. A counter machine is k
-reversal if each counter makes at most k alternations between increasing mode and decreasing mode on any computation, and reversal bounded if it is k-reversal for some k. In this paper we concentrate on the properties of deterministic stateless realtime WK-automata with counters that are reversal
bounded. We give examples and establish hierarchies with respect to counters and reversals.

  • Content Type Journal Article
  • Pages 1-8
  • DOI 10.1007/s11047-011-9290-9
  • Authors
    • László Hegedüs, Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, 4032 Hungary
    • Benedek Nagy, Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, 4032 Hungary
    • Ömer Eğecioğlu, Department of Computer Science, University of California, Santa Barbara, CA 93106, USA

The Deutsch–Jozsa problem: de-quantisation and entanglement

Abstract  The Deutsch–Jozsa problem is one of the most basic ways to demonstrate the power of quantum computation. Consider a Boolean
function f : {0, 1}
n
→ {0, 1} and suppose we have a black-box to compute f. The Deutsch

Abstract  

The Deutsch–Jozsa problem is one of the most basic ways to demonstrate the power of quantum computation. Consider a Boolean
function f : {0, 1}
n
 → {0, 1} and suppose we have a black-box to compute f. The Deutsch–Jozsa problem is to determine if f is constant (i.e.

f(x) = const, “x Î {0,1}n

) or if f is balanced (i.e. f(x) = 0 for exactly half the possible input strings

x Î {0,1}n

) using as few calls to the black-box computing f as is possible, assuming f is guaranteed to be constant or balanced. Classically it appears that this requires at least 2
n−1 + 1 black-box calls in the worst case, but the well known quantum solution solves the problem with probability one in exactly
one black-box call. It has been found that in some cases the algorithm can be de-quantised into an equivalent classical, deterministic
solution. We explore the ability to extend this de-quantisation to further cases, and examine with more detail when de-quantisation
is possible, both with respect to the Deutsch–Jozsa problem, as well as in more general cases.

  • Content Type Journal Article
  • Pages 1-9
  • DOI 10.1007/s11047-011-9276-7
  • Authors
    • Alastair A. Abbott, Department of Computer Science, University of Auckland, Auckland, New Zealand

Quantum computation with write-only memory

Abstract  In classical computation, a “write-only memory” (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic
or probabilistic) classical computer brings no advantage. We prove that quantum computers that a…

Abstract  

In classical computation, a “write-only memory” (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic
or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can
solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource
bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition
of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines
using sublogarithmic amounts of read/write memory are shown to be solvable by these enhanced automata.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-011-9270-0
  • Authors
    • Abuzer Yakaryılmaz, Department of Computer Engineering, Boğaziçi University, Bebek, 34342 İstanbul, Turkey
    • Rūsiņš Freivalds, Institute of Mathematics and Computer Science, University of Latvia, Raiņa Bulvāris 29, Riga, LV-1459 Latvia
    • A. C. Cem Say, Department of Computer Engineering, Boğaziçi University, Bebek, 34342 İstanbul, Turkey
    • Ruben Agadzanyan, Institute of Mathematics and Computer Science, University of Latvia, Raiņa Bulvāris 29, Riga, LV-1459 Latvia

Using enzymatic numerical P systems for modeling mobile robot controllers

Abstract  P systems (PSs) are powerful computing models based on the structure of a biological cell and on the way chemicals interact
in complex biochemical reactions which take place in various compartments (or membranes) of the cell. A lot…

Abstract  

P systems (PSs) are powerful computing models based on the structure of a biological cell and on the way chemicals interact
in complex biochemical reactions which take place in various compartments (or membranes) of the cell. A lot of interest has
been focused on developing various forms of PSs, from cell-like to tissue-like structures. Most of the research effort has
been concentrated on symbolical PSs. Numerical P systems (NPSs) have been introduced in 2006 for possible applications in
economics and business processes but no other structures and applications concerning this type of PSs have been provided since
then. This paper proposes a new class of NPSs, in which enzyme-like variables allow the existence of more than one production
function in each membrane, while keeping the deterministic nature of the system. The way this new type of deterministic NPSs
works and a possible use of it for modeling mobile robot controllers are detailed.

  • Content Type Journal Article
  • Pages 1-7
  • DOI 10.1007/s11047-011-9286-5
  • Authors
    • Ana Brânduşa Pavel, Laboratory of Natural Computing and Robotics, Department of Automatic Control and Systems Engineering, Faculty of Automatic Control and Computers, Politehnica University of Bucharest, Splaiul Independenţei, Nr. 313, Sector 6, 060042 Bucharest, Romania
    • Cătălin Buiu, Laboratory of Natural Computing and Robotics, Department of Automatic Control and Systems Engineering, Faculty of Automatic Control and Computers, Politehnica University of Bucharest, Splaiul Independenţei, Nr. 313, Sector 6, 060042 Bucharest, Romania

Supertasks do not increase computational power

Abstract  It is generally assumed that supertasks increase computational power. It is argued, for example, that supertask machines can
compute beyond the Turing limit, e.g., compute the halting function. We challenge this assumption. We do n…

Abstract  

It is generally assumed that supertasks increase computational power. It is argued, for example, that supertask machines can
compute beyond the Turing limit, e.g., compute the halting function. We challenge this assumption. We do not deny that supertask
machines can compute beyond the Turing limit. Our claim, rather, is that the (hyper) computational power of these machines
is not related to supertasks, but to the “right kind” of computational structure.

  • Content Type Journal Article
  • Pages 1-8
  • DOI 10.1007/s11047-011-9280-y
  • Authors
    • Oron Shagrir, Philosophy and Cognitive Science, The Hebrew University of Jerusalem, Jerusalem, Israel

A Chaitin number based on compressible strings

Abstract  In 1975 Chaitin introduced his

\Upomega

number as a concrete example of random real. The real

\Upomega

is defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a univer…

Abstract  

In 1975 Chaitin introduced his


\Upomega

number as a concrete example of random real. The real


\Upomega

is defined based on the set of all halting inputs for an optimal prefix-free machine U, which is a universal decoding algorithm used to define the notion of program-size complexity. Chaitin showed


\Upomega

to be random by discovering the property that the first n bits of the base-two expansion of


\Upomega

solve the halting problem of U for all binary inputs of length at most n. In this article, we introduce a new variant


\Uptheta

of Chaitin


\Upomega

number. The real


\Uptheta

is defined based on the set of all compressible strings. We investigate the distribution of compressible strings and show
that


\Uptheta

is random. In addition, we generalize


\Uptheta

to


\Uptheta(Q, R)

with reals Q, R > 0 and study its properties. In particular, we show that the computability of the real


\Uptheta(T, 1)

gives a sufficient condition for a real T ∈ (0, 1) to be a fixed point for partial randomness, i.e., to satisfy that the compression rate of T equals to T.

  • Content Type Journal Article
  • Pages 1-12
  • DOI 10.1007/s11047-011-9272-y
  • Authors
    • Kohtaro Tadaki, Research and Development Initiative, Chuo University, JST CREST, 1-13-27 Kasuga, Bunkyo-ku, Tokyo, 112-8551 Japan

Amorphous computing: a research agenda for the near future

Abstract  Amorphous computing presents a novel computational paradigm. The respective computational models have been recently introduced
and studied in a series of works by J. Wiedermann and his Ph.D. student L. Petrů. From a computational …

Abstract  

Amorphous computing presents a novel computational paradigm. The respective computational models have been recently introduced
and studied in a series of works by J. Wiedermann and his Ph.D. student L. Petrů. From a computational viewpoint, amorphous
computing systems differ from the classical ones almost in every aspect: they consist of a set of tiny, independent and self-powered
processors or robots that can communicate wirelessly to a limited distance. The processors are randomly placed in a closed
area or volume and form an ad-hoc network; in some applications they can move, either actively, or passively (e.g., in a bloodstream).
Assuming the exponential progress in all sciences resulting in our ability to produce amorphous computing systems with myriads
of processors, an unmatched application potential is expected profoundly to change all areas of science and life. But prior
to this state of the matters theoretical and practical studies of the computational properties and efficiency of amorphous
computing systems must be performed. It is expected that an indispensable part of computer science will be affected by this
trend.

  • Content Type Journal Article
  • Pages 1-5
  • DOI 10.1007/s11047-011-9281-x
  • Authors
    • Jiří Wiedermann, Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou věží 2, 182 07 Prague 8, Czech Republic

Fermat’s last theorem and chaoticity

Abstract  Proving that a dynamical system is chaotic is a central problem in chaos theory (Hirsch in Chaos, fractals and dynamics, 1985]. In this note we apply the computational method developed in (Calude and Calude in Complex Syst 18:267–…

Abstract  

Proving that a dynamical system is chaotic is a central problem in chaos theory (Hirsch in Chaos, fractals and dynamics, 1985]. In this note we apply the computational method developed in (Calude and Calude in Complex Syst 18:267–285, 2009; Calude and Calude in Complex Syst 18:387–401, 2010; Calude et al in J Multi Valued Log Soft Comput 12:285–307, 2006) to show that Fermat’s last theorem is in the lowest complexity class


\mathfrak CU,1

. Using this result we prove the existence of a two-dimensional Hamiltonian system for which the proof that the system has
a Smale horseshoe is in the class


\mathfrak CU,1

, i.e. it is not too complex.

  • Content Type Journal Article
  • Pages 1-5
  • DOI 10.1007/s11047-011-9282-9
  • Authors
    • Elena Calude, Institute of Information and Mathematical Sciences, Massey University at Albany, Private Bag 102-904, North Shore MSC, New Zealand

A computational journey into the mind

Abstract  The first half of this paper is the written version of the invited talk presented at Unconventional Computing UC10, The University
of Tokyo, Japan, June 21–25, 2010. It describes some salient features of hypercomputation in Dicks…

Abstract  

The first half of this paper is the written version of the invited talk presented at Unconventional Computing UC10, The University
of Tokyo, Japan, June 21–25, 2010. It describes some salient features of hypercomputation in Dickson algebras. Such quadratic
algebras form an appropriate framework for nonlinear computations which does not limit a priori the computational power of multiplication. They underlie paradoxical mathematics whose potential interest to analyse some computational aspects of the human mind which resist the classical approach
is presented. In its last part, the paper offers new glimpses on the organic logic for hypercomputation by developing a fresh
look at plane geometry in relation with the ζ function.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s11047-011-9269-6
  • Authors
    • Françoise Chatelin, CERFACS, 42 Avenue Gaspard Coriolis, 31057 Toulouse Cedex 01, France

Topological Active Volume 3D segmentation model optimized with genetic approaches

Abstract  The Topological Active Volumes is an active model focused on 3D segmentation tasks. It is based on the 2D Topological Active
Nets model and provides information about the surfaces and the inside of the detected objects in the scene…

Abstract  

The Topological Active Volumes is an active model focused on 3D segmentation tasks. It is based on the 2D Topological Active
Nets model and provides information about the surfaces and the inside of the detected objects in the scene. This paper proposes
new optimization approaches based on Genetic Algorithms that improve the results of the 3D segmentations and overcome some
drawbacks of the model related to parameter tuning or noise conditions. The hybridization of the genetic algorithm with a
greedy local search allows the treatment of topological changes in the model, with the possibility of an automatic subdivision
of the Topological Active Volume. This combination integrates the advantages of the global and local search procedures in
the segmentation process.

  • Content Type Journal Article
  • Pages 1-14
  • DOI 10.1007/s11047-011-9275-8
  • Authors
    • Jorge Novo, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 Coruña, Spain
    • Noelia Barreira, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 Coruña, Spain
    • Manuel González Penedo, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 Coruña, Spain
    • José Santos, Department of Computer Science, University of A Coruña, Campus de Elviña s/n, 15071 Coruña, Spain