Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: turing universality

Sortuj według:

Ogranicz wyniki do:

Oritatami System : a Survey and the Impossibility of Simple Simulation at Small Delays

Rogers T. A., Seki S.

Fundamenta Informaticae

2017

Vol. 154, nr 1/4

359--372

RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any oritatami system at larger delay.

Computing Issues of Asynchronous CA

Dennunzio A., Formenti E., Manzoni L.

Fundamenta Informaticae

2012

Vol. 120, nr 2

165-180

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.

Abstract Geometrical Computation 1: Embedding Black Hole Computations with Rational Numbers

Durand-Lose J.

Fundamenta Informaticae

2006

Vol. 74, nr 4

491-510

The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable (R.E.) problem. In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers (and not real numbers), has the same property: it can simulate any Turing machine and can decide any R.E.problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect.