Titlebook: Machines, Computations, and Universality; 4th International Co Maurice Margenstern Conference proceedings 2005 Springer-Verlag Berlin Heide

conquer

CERE

不理会

Algorithmic Randomness, Quantum Physics, and Incompletenesss? Can quantum randomness be used to trespass the Turing’s barrier? Can complexity shed more light on incompleteness? In this paper we use variants of “algorithmic complexity” to discuss the above questions.

吹气

过渡时期

Universality and Cellular Automatamputational Equivalence”. We discuss a classification for cellular automata that is based on computably enumerable degrees. In this setting the full structure of the semilattice of the c.e. degrees is inherited by the cellular automata.

Congruous

overhaul

Computational Completeness of P Systems with Active Membranes and Two Polarizationse membrane system, and of type . i.e., communication rules sending out an object of a membrane thereby possibly changing the polarization of this membrane, assigned to at most two membranes are shown to be computationally complete, which improves the previous result of this type with respect to the

crumble

原始

盲信者

Real Recursive Functions and Real Extensions of Recursive Functionsunctions containing some basic functions and closed by composition and linear integration..We extend this result to . computable functions: functions over the reals that extend total recursive functions over the integers are proved to correspond to the smallest class of real functions containing som