First Advisor

Melanie Mitchell

Date of Publication

1-1-2011

Document Type

Dissertation

Degree Name

Doctor of Philosophy (Ph.D.) in Computer Science

Department

Computer Science

Language

English

Subjects

Cellular automata, Information filtering systems, Information storage and retrieval systems

DOI

10.15760/etd.275

Physical Description

1 online resource (xx, 182 p.) : ill.

Abstract

Cellular automata (CA) have been widely used as idealized models of spatially-extended dynamical systems and as models of massively parallel distributed computation devices. Despite their wide range of applications and the fact that CA are capable of universal computation (under particular constraints), the full potential of these models is unrealized to-date. This is for two reasons: (1) the absence of a programming paradigm to control these models to solve a given problem and (2) the lack of understanding of how these models compute a given task. This work addresses the notion of computation in two-dimensional cellular automata. Solutions using a decentralized parallel model of computation require information processing on a global level. CA have been used to solve the so-called density (or majority) classification task that requires a system-wide coordination of cells. To better understand and challenge the ability of CA to solve problems, I define, solve, and analyze novel tasks that require solutions with global information processing mechanisms. The ability of CA to perform parallel, collective computation is attributed to the complex pattern-forming system behavior. I further develop the computational mechanics framework to study the mechanism of collective computation in two-dimensional cellular automata. I define several approaches to automatically identify the spatiotemporal structures with information content. Finally, I demonstrate why an accurate model of information processing in two-dimensional cellular automata cannot be constructed from the space-time behavior of these structures.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Comments

Portland State University. Dept. of Computer Science

Persistent Identifier

http://archives.pdx.edu/ds/psu/7047

Download

Share

COinS