Textbook in PDF format

Did you know that computation can be implemented with cytoskeleton networks, chemical reactions, liquid marbles, plants, polymers and dozens of other living and inanimate substrates? Do you know what is reversible computing or a DNA microscopy? Are you aware that randomness aids computation? Would you like to make logical circuits from enzymatic reactions? Have you ever tried to implement digital logic with Minecraft? Do you know that eroding sandstones can compute too?This volume reviews most of the key attempts in coming up with an alternative way of computation. In doing so, the authors show that we do not need computers to compute and we do not need computation to infer. It invites readers to rethink the computer and computing, and appeals to computer scientists, mathematicians, physicists and philosophers. The topics are presented in a lively and easily accessible manner and make for ideal supplementary reading across a broad range of subjects.
Theory
Mapping the Territory of Computation Including Embodied Computation
Unconventional Computation
Implications
Computation in General
Topology of information representation
Topology of information processing
Programmability
Universality
Embodied Computation
Definition
Physics for computational purposes
Transduction
Analog computation
Quantum computation
Field computation
Computation for physical purposes
Programmable Matter
Artificial Morphogenesis
Conclusions
Reversible Logic Element with Memory as an Alternative Logical Device
Reversible Logic Element with Memory (RLEM)
Definition of a reversible logic element with memory
Rotary element (RE), a typical RLEM
Constructing reversible machines by REs
All Non-degenerate -State RLEMs Except Four are Universal
Realizing RLEMs in Reversible Environments
RLEMs in the billiard ball model
RLEM in a simple reversible cellular automaton
Concluding Remarks
Space Bounded Scatter Machines
First Concepts and Promised Results
The Experiment, the Protocols and the Machine
The Standard Scatter Machine
Probabilistic trees
Sparse oracles
Coding and decoding the vertex position
Lower bounds
Upper bounds
The Generalized Scatter Machine
Lower bounds
Upper bounds
Exclusively Quantum: Computations Only Possible on a Quantum Computer
Background: Parallelism and Quantum Theory
On the importance of parallelism
Quantum computation and quantum information
The qubit
Measurements
Putting qubits together
Entanglement
Some History
Quantum versus classical computation
A review of previous results
True randomness
Entangled states
Quantum speed-up
Quantum simulations
QTM versus DTM and PTM
Quantum versus classical complexity
Super-Turing computations
Unconventional Computations and Non-universality
Evolving Computations
Evolving computational complexity
Rank-varying computational complexity
Time-varying computational complexity
Evolving computational variables
Time-varying variables
Interacting variables
Computations obeying a global constraint
Quantum Fourier Transform
Rank-varying complexity
Semi-classical solution
Parallel approach
Quantum decoherence
Time-varying variables
Quantum Error-correction
Quantum codes
Time-varying complexity
Error correction via symmetrization
Entanglement Revisited
Interacting variables
Quantum distinguishability
Generalization
Another approach to distinguishability
Some consequences
Conveying quantum information through a classical channel
Protecting quantum information from classical attacks
Transformations obeying a global constraint
Estimations of Integrated Information Based on Algorithmic Complexity and Dynamic Querying
Basic Concepts of Integrated Information Theory
Calculus of ϕ
Methods
Programmability test and meta-test
Causal perturbation analysis
Causal influence and sublog program-size divergence
A simplicity versus complexity test
Numerical Results
Compression sensitivity as informative of integration
Finding simple rules in complex behavior
Simple rules and the black pattern of distribution of information
Automatic meta-perturbation test
Shrinking after dividing to rule
Limitations
Conclusions and Future Directions
Appendix A
A How a meta-perturbation test works
Appendix B
Robot Narratives
Robots Explore an Alien Planet
Prologue
Greek Olympus, narrative robots
Roman Olympus, declarative robots
Epilogue
Robot Imaginations
Dennett’s Tower
Robots in the tower
An architecture for an ethical Popperian robot
From Popperian to Gregorian robots
Narrative logic
Gregorian Chat
The narrative hypothesis in more detail
The Gregorian chat system
Robot architecture
Hybrid physical/virtual environment architecture
Testing the narrative hypothesis in a robot ecology
Extensions of the approach
Discussion and Conclusions
Communication and cognition
Social robots
Narrative logic and its interface with world modeling in artificial intelligence
Beyond a “repository of actions”: The particular and the general in narrative
Story generator and story parser
Preparing for the future
Evolving Boolean Regulatory Networks with Variable Gene Expression Times
The RBNK Model
The RBNK Model with Variable Gene Expression Times
Gene expression
Experimentation
Asynchronous experimentation
Variable Sized GRN with Variable Gene Expression Times
Emergent complexity
Experimentation
Conclusions
Membrane Computing Concepts, Theoretical Developments and Applications
Types of P Systems
Preliminaries
Transition P systems
P systems with active membranes
Communication P systems
Tissue-like P systems with symport/antiport rules
Spiking neural P systems
Enzymatic numerical P systems
Computing Power and Computational Efficiency
Computing power
Rewriting membrane systems
Computational efficiency
Recognizer membrane systems
Polynomial time complexity classes
Limits on efficient computations
Solving computationally hard problems
Applications of Membrane Computing
Modeling ecosystems with population dynamics P systems
Path planning and control of mobile robots
Fault diagnosis with spiking neural P systems
Other applications
Concluding remarks
Implementation of P Systems
Software implementations
GPU-based hardware implementations
GPU computing
GPU simulators of P systems
FPGA-based hardware implementations
Discussion
Concluding Remarks
Computing with Modest Resources: How to Have Your Cake and Eat it Too
Why Bigger is Not Necessarily Smarter
Why Smaller Might be Smarter
What is External Drive and How Does It Help
A Thought Experiment: Maxwell’s Daemon Rebooted
Example: Memristor Networks
Memristor model
Conclusions
Physical Randomness Can Help in Computations
Randomness is Important
How Can We Describe Randomness in Precise Terms?
Back to Physics
How Does This Affect Computations
Probabilistic Logic Gate in Asynchronous Game of Life with Critical Property
Asynchronous Game of Life and its Logic Gates
Phase transition and criticality
Computation by asynchronous GL
Logic gate in asynchronous GL
Discussion
Acknowledgements
A Mystery of Human Biological Development — Can It Be Used to Speed up Computations?
Formulation of the Problem
Exponential Speedup Phenomenon: A Brief History and a Brief Description
Symmetric Automata and Computations
Structure of Abstract Automata and Instruction Machines
Structure of Symmetric Automata and Machines
Functional Characteristics of Operationally Symmetric Turing Machines
Computation By Biological Means
Computation
Use of biology for computation
What can biocomputers do?
DNA Computing
Origins of DNA computing
Computing with DNA
Adleman’s experiment
Sticker systems
Recent progress on computational power of DNA
Limitations of DNA
Computation with Slime Mould
Introduction to slime moulds
Slime moulds for computational tasks
Amoeboid organisms as a computer
Slime moulds as a form of computation
Select applications of slime moulds
Challenges of computing with slime moulds
Computation with Motile Biological Agents
Molecular motors
Use of biological motion in confined structures
Issues with mobile biologicals
Computation with Synthetic Biology
Chemotaxis
Saccharum saccharomyces and genetic toggles
Cellular computation
Multicellular machines
Differences in Biological Computing Paradigms
Discussion
Critical research gaps in biological computing
The case for biosupremacy
Swarm and Stochastic Computing for Global Optimization
Optimization
Stochastic Enhancements
Evolutionary Computation
Nature-Inspired Computing
Non-SI-based approaches
SI-based approaches
Discussions
Vector Computation
Epistemology versus Ontology in the Quantum Computation Context
Types of Quantum Oracles for Randomness: Pure States in a Superposition Versus Mixed States
Questionable Parallelism by Views on a Vector
Computation by Projective Measurements of Partitioned State Space
Entanglement as Relational Parallelism Across Multi-Partite States
On Partial Views of Vectors
Unsupervised Learning Approach Using Reinforcement Techniques on Bio-inspired Topologies
Molecular networks
Cellular automata
Conway’s Game-of-Life
Neuromorphic computing systems
Molecular-based Topology
Artificial Neural Networks
Neuron Model
Simple Izhikevich model
Excitation Reinforcement
Majority-rule
Game-of-Life rule
Unsupervised Learning
Majority-rule learning
Game-of-Life learning
Hebbian learning
Training and Classification
Results
Discussion
Acknowledgement
Intelligent Gamesourcing — Artificial Intelligence in Problem Solution by Game Playing
Gamesourcing
History
Motivation
Leisure
Game playing
Paradigm
Structure
Fun
Credibility of outputs
Evaluation of success
Current status
Astro Drone
EteRNA
Foldit
Play to cure: Genes in space
Sea Hero Quest
Application — People versus Differential Evolution in Search of the Shortest Path
Volume : Implementations
From Oscillatory Reactionsto Robotics: A Serendipitous Journey Through Chemistry, Physics and Computation
Systems Dynamics as a Computational Platform
Wet oscillating systems
Electrochemical oscillators
Computation and Control in Dynamic Systems
Computation in memristive devices and systems
Logic design with memristors/memristive devices
Matrix vector multiplication
Hardware artificial neural networks
Principles of control in dynamic systems — PID case
Reservoir computing
Reservoir computing and control systems
Controllers Beyond PID: Fuzzy and Neuromorphic
Fuzzy logic
Processing fuzzy logic by using molecules
Implementation of fuzzy logic systems in solid-state devices
Neuromorphic devices
Alternative Computing in Autonomous Robotics
Amoeba-based solution search system and electronic amoeba
Amoeba-inspired autonomously walking robot
Physicality for the identification of ground condition
Integration of reinforcement learning for efficient walking
Alternative Computing and Soft Robotics
Concluding Remarks
Computing by Chemistry: The Native Chemical Automata
A Brief History
How Native Chemical Automata are Built in Practice
Selecting the language-automata pair, and the chemistry
Initial conditions and alphabet symbol assignment
Recipe quantification and selection of time interval
Accept/reject criteria optimization
Reconfiguration and Variants/Extension of Native Chemical Automata
Inclusive hierarchy and automata reconfigurability
Extension to continuous operation (CSTR reactor)
Coupling of Belousov–Zhabotinsky to self-assembly
Conclusions and Outlook
Discovering Boolean Functions on Actin Networks
The Actin Network
Spike-based Gates
Automaton model
Interfacing with the network
Maximizing a number of logical gates
Actin droplet machine
Voltage-based Gates
The model
Extension to bundle networks
The network
Preliminary results
Results
Ideal electrodes
Boolean gates
Realistic electrodes
Finite state machine
Using two values of k = and k =
Discussion
Implication and Not-Implication Boolean Logic Gates Mimicked with Enzyme Reactions — General Approach and Application to Signal-Triggered Biomolecule Release Processes
Mimicking IMPLY Logic Gate
Mimicking INHIB Logic Gate
Using the IMPLY and INHIB Logic Gates for Stimulating Molecule Release Function
Conclusions
Appendix
Molecular Computation via Polymerase Strand Displacement Reactions
Logic circuits
Chemical reaction networks
organization
Strand Displacement
Using Strand Displacing Polymerase for Computation
CRNs Using Strand Displacing Polymerase
Methods and Protocol
Oligonucleotide design, synthesis, and purification
Fluorescence sample preparation and measurement
Discussion and Outlook
Optics-Free Imaging with DNA Microscopy: An Overview
DNA Microscopy for Surface D Imaging
DNA Microscopy for Volumetric D Imaging
Conclusions and Outlook
Fully Analog Memristive Circuits for Optimization Tasks: A Comparison
Dynamical Equation for Memristor Circuits
Single memristor and Lyapunov function
Circuits
Lyapunov function for memristor circuits
Number of fixed points and stability
Analysis and Comparisons
The instances
Minimization of the continuous Lyapunov function
Conclusions
Organic Memristive Devices for Bio-inspired Applications
Organic Memristive Device
Adaptive Circuits
Relationship of Optical and Electrical Properties
Neuromorphic Applications
Frequency dependent plasticity
Nervous system mimicking circuits
Towards synapse prosthesis
Stochastic self-organized computational systems
Conclusions
On Wave-Based Majority Gates with Cellular Automata
Propagation Patterns in Life-like Rules
MAJORITY Gates by Competing Patterns
Final Notes
Information Processing in Plants: Hormones as Integrators of External Cues into Plant Development
Hormonal Encoding of Environmental Information
Self-regulatory Hormonal Network Underlying Plasticity in Plant Development
Information processing in the transition from dormancy to germination
Concluding Remarks
Hybrid Computer Approach to Train a Machine Learning System
A brief introduction to artificial intelligence and machine learning
Analog versus digital computing
Balancing an inverse pendulum using reinforcement learning
The Analog Simulation
The Reinforcement Learning System
Value function
Q-learning algorithm
Python implementation
States
Actions
Modeling the action value function Q(s, a)
Feature transformation to avoid underfitting
Decaying α and ε to improve learning and to avoid overfitting
Hybrid interface
Results
Acknowledgement
On the Optimum Geometry and Training Strategy for Chemical Classifiers that Recognize the Shape of a Sphere
The Evolutionary Optimization of Chemical Classifiers
Results
Conclusions
Sensing and Computing with Liquid Marbles
Collision-based Gate
Belousov–Zhabotinsky Cargo
Photosensor
Thermal Sensor
Robot Controller
Neuromorphic Marbles
Discussion
Towards Colloidal Droplet Processors
Background
Data throughput
Heat dissipation
Energy consumption
Liquid Droplet Computer
Holonomic processors
Colloidal Processors
Phase change architectures
Microfluidic circuits
Layered shells
Granular media, foams, and plasmas
Biological Processors
Conclusions
Biomolecular Motor-based Computing
Applications of Biomolecular Motors in Computing
Parallel computing using biomolecular motors in nanofabricated networks
Computing using swarm robots prepared from biomolecular motors
Design and construction of molecular robots
Swarming of molecular robots
Controlling the shape morphology of swarms of molecular robots
Remote control of the swarming of molecular robots
Logical operation of molecular robots
Orthogonal swarming of molecular robots
Conclusions and Future Perspectives
Computing with Square Electromagnetic Pulses
Background
Brief historical retrospective
Basics of transmission line theory
Method
Main computing elements: Cross-points
Four-point crossing: Catt’s junction
Scattering matrix approach
Multi-way junctions: Series and parallel
Simulation results
Scaling down geometries
Pulse generation and control requirements
Future Directions
D-based structures
Graph-based computing
More complex signals and materials
Acknowledgements
Creative Quantum Computing: Inverse FFT Sound Synthesis, Adaptive Sequencing and Musical Composition
Why Quantum Computer Music?
Algorithmic Music
qSyn: Inverse FFT Sound Synthesis
qSeq: Adaptive Musical Sequencer
The Composition Zeno
Concluding Remarks
Appendix
Logical Gates in Natural Erosion of Sandstone
Modeling of Natural Erosion
Specific Parameters
Gates
AND gate
XOR gate
One-bit half-adder
Discussion
Supplementary Materials
A Case of Toy Computing Implementing Digital Logics with “Minecraft”
History and Theory of Toy Computing
Digital Logics in “Minecraft”
Signal generation and transportation
NAND gates
Digital Circuits in “Minecraft” and the Remains of Electronics
The circuit
The 4-bit full adder build with TTL-logic
The 4-bit full adder build in “Minecraft”
Project Discussion
Building a BCD decoder in “Minecraft”
The computational labyrinth
Walking the way of the signal
Evolving Conductive Polymer Neural Networks on Wetware
Introduction of Polymer Neural Networks
Electropolymerisation of Conducting Polymer Wire
Polymer wire growth
Wire diameter and growth rate
Conductance increase of wires
Directional growth of wire and D growth
Machine Learning for Polymer Wire Growth
Supervised learning: Simple perceptron for simple logic gates
Unsupervised learning: Autoencoder for feature extraction
Conclusions