Handbook of Unconventional Computing: Theory / Implementations (2-Volume Set)

Volume 1 : Theory
Contents
Preface
Chapter 1. Mapping the Territory of Computation Including Embodied Computation
1.1. Unconventional Computation
1.1.1. Implications
1.2. Computation in General
1.2.1. Topology of information representation
1.2.2. Topology of information processing
1.2.3. Programmability
1.2.4. Universality
1.3. Embodied Computation
1.3.1. Definition
1.3.2. Physics for computational purposes
1.3.2.1. Transduction
1.3.2.2. Analog computation
1.3.2.3. Quantum computation
1.3.2.4. Field computation
1.3.3. Computation for physical purposes
1.4. Programmable Matter
1.5. Artificial Morphogenesis
1.6. Conclusions
References
Chapter 2. Reversible Logic Element with Memory as an Alternative Logical Device
2.1. Introduction
2.2. Reversible Logic Element with Memory (RLEM)
2.2.1. Definition of a reversible logic element with memory
2.2.2. Rotary element (RE), a typical RLEM
2.2.3. Constructing reversible machines by REs
2.3. All Non-degenerate 2-State RLEMs Except Four are Universal
2.4. Realizing RLEMs in Reversible Environments
2.4.1. RLEMs in the billiard ball model
2.4.2. RLEM in a simple reversible cellular automaton
2.5. Concluding Remarks
References
Chapter 3. Space Bounded Scatter Machines
3.1. Introduction
3.2. First Concepts and Promised Results
3.3. The Experiment, the Protocols and the Machine
3.4. The Standard Scatter Machine
3.4.1. Probabilistic trees
3.4.2. Sparse oracles
3.4.3. Coding and decoding the vertex position
3.4.4. Lower bounds
3.4.5. Upper bounds
3.5. The Generalized Scatter Machine
3.5.1. Lower bounds
3.5.2. Upper bounds
3.6. Conclusion
Acknowledgments
References
Chapter 4. Exclusively Quantum: Computations Only Possible on a Quantum Computer
4.1. Introduction
4.2. Background: Parallelism and Quantum Theory
4.2.1. On the importance of parallelism
4.2.2. Quantum computation and quantum information
4.2.2.1. The qubit
4.2.2.2. Measurements
4.2.2.3. Putting qubits together
4.2.2.4. Entanglement
4.3. Some History
4.3.1. Quantum versus classical computation
4.3.2. A review of previous results
4.3.2.1. True randomness
4.3.2.2. Entangled states
4.3.2.3. Quantum speed-up
4.3.2.4. Quantum simulations
4.3.2.5. QTM versus DTM and PTM
4.3.2.6. Quantum versus classical complexity
4.3.2.7. Super-Turing computations
4.4. Unconventional Computations and Non-universality
4.5. Evolving Computations
4.5.1. Evolving computational complexity
4.5.1.1. Rank-varying computational complexity
4.5.1.2. Time-varying computational complexity
4.5.2. Evolving computational variables
4.5.2.1. Time-varying variables
4.5.2.2. Interacting variables
4.5.2.3. Computations obeying a global constraint
4.6. Quantum Fourier Transform
4.6.1. Rank-varying complexity
4.6.2. Semi-classical solution
4.6.3. Parallel approach
4.6.4. Quantum decoherence
4.6.5. Time-varying variables
4.7. Quantum Error-correction
4.7.1. Quantum codes
4.7.2. Time-varying complexity
4.7.3. Error correction via symmetrization
4.8. Entanglement Revisited
4.8.1. Interacting variables
4.8.2. Quantum distinguishability
4.8.2.1. Generalization
4.8.3. Another approach to distinguishability
4.8.4. Some consequences
4.8.4.1. Conveying quantum information through a classical channel
4.8.4.2. Protecting quantum information from classical attacks
4.8.5. Transformations obeying a global constraint
4.9. Conclusion
References
Chapter 5. Estimations of Integrated Information Based on Algorithmic Complexity and Dynamic Querying
5.1. Introduction
5.2. Basic Concepts of Integrated Information Theory
5.2.1. Calculus of ϕ
5.3. Methods
5.3.1. Programmability test and meta-test
5.3.2. Causal perturbation analysis
5.3.3. Causal influence and sublog program-size divergence
5.3.4. A simplicity versus complexity test
5.4. Numerical Results
5.4.1. Compression sensitivity as informative of integration
5.4.2. Finding simple rules in complex behavior
5.4.3. Simple rules and the black pattern of distribution of information
5.4.3.1. Automatic meta-perturbation test
5.4.3.2. Shrinking after dividing to rule
5.4.4. Limitations
5.5. Conclusions and Future Directions
References
Appendix A
A.1. How a meta-perturbation test works
Appendix B
Chapter 6. Robot Narratives
6.1. Introduction
6.2. Robots Explore an Alien Planet
6.2.1. Prologue
6.2.2. Greek Olympus, narrative robots
6.2.3. Roman Olympus, declarative robots
6.2.4. Epilogue
6.3. Robot Imaginations
6.3.1. Dennett’s Tower
6.3.2. Robots in the tower
6.3.3. An architecture for an ethical Popperian robot
6.3.4. From Popperian to Gregorian robots
6.3.5. Narrative logic
6.4. Gregorian Chat
6.4.1. The narrative hypothesis in more detail
6.4.2. The Gregorian chat system
6.4.2.1. Robot architecture
6.4.2.2. Hybrid physical/virtual environment architecture
6.4.3. Testing the narrative hypothesis in a robot ecology
6.4.4. Extensions of the approach
6.5. Discussion and Conclusions
6.5.1. Communication and cognition
6.5.2. Social robots
6.5.3. Narrative logic and its interface with world modeling in artificial intelligence
6.5.4. Beyond a “repository of actions”: The particular and the general in narrative
6.5.5. Story generator and story parser
6.5.6. Preparing for the future
Acknowledgments
References
Chapter 7. Evolving Boolean Regulatory Networks with Variable Gene Expression Times
7.1. Introduction
7.2. The RBNK Model
7.3. The RBNK Model with Variable Gene Expression Times
7.3.1. Gene expression
7.3.2. Experimentation
7.3.3. Asynchronous experimentation
7.4. Variable Sized GRN with Variable Gene Expression Times
7.4.1. Emergent complexity
7.4.2. Experimentation
7.5. Conclusions
References
Chapter 8. Membrane Computing Concepts, Theoretical Developments and Applications
8.1. Introduction
8.2. Types of P Systems
8.2.1. Preliminaries
8.2.2. Transition P systems
8.2.3. P systems with active membranes
8.2.4. Communication P systems
8.2.5. Tissue-like P systems with symport/antiport rules
8.2.6. Spiking neural P systems
8.2.7. Enzymatic numerical P systems
8.3. Computing Power and Computational Efficiency
8.3.1. Introduction
8.3.2. Computing power
8.3.2.1. Rewriting membrane systems
8.3.3. Computational efficiency
8.3.3.1. Recognizer membrane systems
8.3.3.2. Polynomial time complexity classes
8.3.3.3. Limits on efficient computations
8.3.3.4. Solving computationally hard problems
8.4. Applications of Membrane Computing
8.4.1. Modeling ecosystems with population dynamics P systems
8.4.2. Path planning and control of mobile robots
8.4.3. Fault diagnosis with spiking neural P systems
8.4.4. Other applications
8.4.5. Concluding remarks
8.5. Implementation of P Systems
8.5.1. Software implementations
8.5.2. GPU-based hardware implementations
8.5.2.1. GPU computing
8.5.2.2. GPU simulators of P systems
8.5.3. FPGA-based hardware implementations
8.5.4. Discussion
8.6. Concluding Remarks
References
Chapter 9. Computing with Modest Resources: How to Have Your Cake and Eat it Too
9.1. Introduction
9.2. Why Bigger is Not Necessarily Smarter
9.3. Why Smaller Might be Smarter
9.4. What is External Drive and How Does It Help
9.5. A Thought Experiment: Maxwell’s Daemon Rebooted
9.6. Example: Memristor Networks
9.6.1. Memristor model
9.7. Conclusions
References
Chapter 10. Physical Randomness Can Help in Computations
10.1. Introduction
10.2. Randomness is Important
10.3. How Can We Describe Randomness in Precise Terms?
10.4. Back to Physics
10.5. How Does This Affect Computations
Acknowledgments
References
Chapter 11. Probabilistic Logic Gate in Asynchronous Game of Life with Critical Property
11.1. Introduction
11.2. Asynchronous Game of Life and its Logic Gates
11.2.1. Phase transition and criticality
11.2.2. Computation by asynchronous GL
11.2.3. Logic gate in asynchronous GL
11.3. Discussion
11.4. Conclusion
Acknowledgements
References
Chapter 12. A Mystery of Human Biological Development — Can It Be Used to Speed up Computations?
12.1. Formulation of the Problem
12.2. Exponential Speedup Phenomenon: A Brief History and a Brief Description
Acknowledgments
References
Chapter 13. Symmetric Automata and Computations
13.1. Introduction
13.2. Structure of Abstract Automata and Instruction Machines
13.3. Structure of Symmetric Automata and Machines
13.4. Functional Characteristics of Operationally Symmetric Turing Machines
13.5. Conclusion
References
Chapter 14. Computation By Biological Means
14.1. Introduction
14.1.1. Computation
14.1.2. Use of biology for computation
14.1.3. What can biocomputers do?
14.2. DNA Computing
14.2.1. Origins of DNA computing
14.2.2. Computing with DNA
14.2.3. Adleman’s experiment
14.2.4. Sticker systems
14.2.5. Recent progress on computational power of DNA
14.2.6. Limitations of DNA
14.3. Computation with Slime Mould
14.3.1. Introduction to slime moulds
14.3.2. Slime moulds for computational tasks
14.3.3. Amoeboid organisms as a computer
14.3.4. Slime moulds as a form of computation
14.3.5. Select applications of slime moulds
14.3.6. Challenges of computing with slime moulds
14.4. Computation with Motile Biological Agents
14.4.1. Molecular motors
14.4.2. Use of biological motion in confined structures
14.4.3. Issues with mobile biologicals
14.5. Computation with Synthetic Biology
14.5.1. Chemotaxis
14.5.2. Saccharum saccharomyces and genetic toggles
14.5.3. Cellular computation
14.5.4. Multicellular machines
14.6. Differences in Biological Computing Paradigms
14.7. Discussion
14.7.1. Critical research gaps in biological computing
14.7.2. The case for biosupremacy
References
Chapter 15. Swarm and Stochastic Computing for Global Optimization
15.1. Introduction
15.2. Optimization
15.3. Stochastic Enhancements
15.4. Evolutionary Computation
15.5. Nature-Inspired Computing
15.5.1. Non-SI-based approaches
15.5.2. SI-based approaches
15.6. Discussions
References
Chapter 16. Vector Computation
16.1. Epistemology versus Ontology in the Quantum Computation Context
16.2. Types of Quantum Oracles for Randomness: Pure States in a Superposition Versus Mixed States
16.3. Questionable Parallelism by Views on a Vector
16.4. Computation by Projective Measurements of Partitioned State Space
16.5. Entanglement as Relational Parallelism Across Multi-Partite States
16.6. On Partial Views of Vectors
16.7. Summary
Acknowledgments
References
Chapter 17. Unsupervised Learning Approach Using Reinforcement Techniques on Bio-inspired Topologies
17.1. Introduction
17.1.1. Molecular networks
17.1.2. Cellular automata
17.1.3. Conway’s Game-of-Life
17.1.4. Neuromorphic computing systems
17.2. Molecular-based Topology
17.3. Artificial Neural Networks
17.4. Neuron Model
17.4.1. Simple Izhikevich model
17.5. Excitation Reinforcement
17.5.1. Majority-rule
17.5.2. Game-of-Life rule
17.6. Unsupervised Learning
17.6.1. Majority-rule learning
17.6.2. Game-of-Life learning
17.6.3. Hebbian learning
17.7. Training and Classification
17.8. Results
17.9. Discussion
Acknowledgement
References
Chapter 18. Intelligent Gamesourcing — Artificial Intelligence in Problem Solution by Game Playing
18.1. Introduction
18.1.1. Gamesourcing
18.1.2. History
18.2. Motivation
18.2.1. Leisure
18.2.2. Game playing
18.2.3. Paradigm
18.2.4. Structure
18.2.5. Fun
18.2.6. Credibility of outputs
18.2.7. Evaluation of success
18.2.8. Current status
18.2.8.1. 1.4.1 Astro Drone
18.2.8.2. EteRNA
18.2.8.3. Foldit
18.2.8.4. Play to cure: Genes in space
18.2.8.5. Sea Hero Quest
18.3. Application — People versus Differential Evolution in Search of the Shortest Path
Acknowledgment
References
Index
Volume 2 : Implementations
Contents
Preface
Chapter 1. From Oscillatory Reactionsto Robotics: A Serendipitous Journey Through Chemistry, Physics and Computation
1.1. Introduction
1.2. Systems Dynamics as a Computational Platform
1.2.1. Wet oscillating systems
1.2.2. Electrochemical oscillators
1.3. Computation and Control in Dynamic Systems
1.3.1. Computation in memristive devices and systems
1.3.1.1. Logic design with memristors/memristive devices
1.3.1.2. Matrix vector multiplication
1.3.1.3. Hardware artificial neural networks
1.3.2. Principles of control in dynamic systems — PID case
1.3.3. Reservoir computing
1.3.4. Reservoir computing and control systems
1.4. Controllers Beyond PID: Fuzzy and Neuromorphic
1.4.1. Fuzzy logic
1.4.2. Processing fuzzy logic by using molecules
1.4.3. Implementation of fuzzy logic systems in solid-state devices
1.4.4. Neuromorphic devices
1.5. Alternative Computing in Autonomous Robotics
1.5.1. Amoeba-based solution search system and electronic amoeba
1.5.2. Amoeba-inspired autonomously walking robot
1.5.3. Physicality for the identification of ground condition
1.5.4. Integration of reinforcement learning for efficient walking
1.6. Alternative Computing and Soft Robotics
1.7. Concluding Remarks
Acknowledgments
References
Chapter 2. Computing by Chemistry: The Native Chemical Automata
2.1. Introduction
2.2. A Brief History
2.3. How Native Chemical Automata are Built in Practice
2.3.1. Selecting the language-automata pair, and the chemistry
2.3.2. Initial conditions and alphabet symbol assignment
2.3.3. Recipe quantification and selection of time interval
2.3.4. Accept/reject criteria optimization
2.4. Reconfiguration and Variants/Extension of Native Chemical Automata
2.4.1. Inclusive hierarchy and automata reconfigurability
2.4.2. Extension to continuous operation (CSTR reactor)
2.4.3. Coupling of Belousov–Zhabotinsky to self-assembly
2.5. Conclusions and Outlook
References
Chapter 3. Discovering Boolean Functions on Actin Networks
3.1. Introduction
3.2. The Actin Network
3.3. Spike-based Gates
3.3.1. Automaton model
3.3.2. Interfacing with the network
3.3.3. Maximizing a number of logical gates
3.3.4. Actin droplet machine
3.4. Voltage-based Gates
3.4.1. The model
3.4.2. Extension to bundle networks
3.4.3. The network
3.4.4. Preliminary results
3.4.5. Results
3.4.5.1. Ideal electrodes
3.4.5.2. Boolean gates
3.4.5.3. Realistic electrodes
3.4.6. Finite state machine
3.4.6.1. Using two values of k = 4 and k = 6
3.5. Discussion
Acknowledgments
References
Chapter 4. Implication and Not-Implication Boolean Logic Gates Mimicked with Enzyme Reactions — General Approach and Application to Signal-Triggered Biomolecule Release Processes
4.1. Introduction
4.2. Mimicking IMPLY Logic Gate
4.3. Mimicking INHIB Logic Gate
4.4. Using the IMPLY and INHIB Logic Gates for Stimulating Molecule Release Function
4.5. Conclusions
Appendix
Acknowledgments
References
Chapter 5. Molecular Computation via Polymerase Strand Displacement Reactions
5.1. Introduction
5.1.1. Logic circuits
5.1.2. Chemical reaction networks
5.1.3. Chapter organization
5.2. Strand Displacement
5.3. Using Strand Displacing Polymerase for Computation
5.4. CRNs Using Strand Displacing Polymerase
5.5. Methods and Protocol
5.5.1. Oligonucleotide design, synthesis, and purification
5.5.2. Fluorescence sample preparation and measurement
5.6. Discussion and Outlook
References
Chapter 6. Optics-Free Imaging with DNA Microscopy: An Overview
6.1. Introduction
6.2. DNA Microscopy for Surface 2D Imaging
6.3. DNA Microscopy for Volumetric 3D Imaging
6.4. Conclusions and Outlook
Acknowledgments
References
Chapter 7. Fully Analog Memristive Circuits for Optimization Tasks: A Comparison
7.1. Introduction
7.2. Dynamical Equation for Memristor Circuits
7.2.1. Single memristor and Lyapunov function
7.2.2. Circuits
7.2.3. Lyapunov function for memristor circuits
7.2.4. Number of fixed points and stability
7.3. Analysis and Comparisons
7.3.1. The instances
7.3.2. Minimization of the continuous Lyapunov function
7.4. Conclusions
Acknowledgments
References
Chapter 8. Organic Memristive Devices for Bio-inspired Applications
8.1. Introduction
8.2. Organic Memristive Device
8.3. Adaptive Circuits
8.4. Relationship of Optical and Electrical Properties
8.5. Neuromorphic Applications
8.5.1. Frequency dependent plasticity
8.5.2. Nervous system mimicking circuits
8.5.3. Towards synapse prosthesis
8.5.4. Stochastic self-organized computational systems
8.6. Conclusions
References
Chapter 9. On Wave-Based Majority Gates with Cellular Automata
9.1. Introduction
9.2. Propagation Patterns in Life-like Rules
9.3. MAJORITY Gates by Competing Patterns
9.4. Final Notes
References
Chapter 10. Information Processing in Plants: Hormones as Integrators of External Cues into Plant Development
10.1. Introduction
10.2. Hormonal Encoding of Environmental Information
10.3. Self-regulatory Hormonal Network Underlying Plasticity in Plant Development
10.3.1. Information processing in the transition from dormancy to germination
10.4. Concluding Remarks
References
Chapter 11. Hybrid Computer Approach to Train a Machine Learning System
11.1. Introduction
11.1.1. A brief introduction to artificial intelligence and machine learning
11.1.2. Analog versus digital computing
11.1.3. Balancing an inverse pendulum using reinforcement learning
11.2. The Analog Simulation
11.3. The Reinforcement Learning System
11.3.1. Value function
11.3.2. Q-learning algorithm
11.3.3. Python implementation
11.3.3.1. States
11.3.3.2. Actions
11.3.3.3. Modeling the action value function Q(s, a)
11.3.3.4. Feature transformation to avoid underfitting
11.3.3.5. Decaying α and ε to improve learning and to avoid overfitting
11.3.4. Hybrid interface
11.4. Results
Acknowledgement
References
Chapter 12. On the Optimum Geometry and Training Strategy for Chemical Classifiers that Recognize the Shape of a Sphere
12.1. Introduction
12.2. The Evolutionary Optimization of Chemical Classifiers
12.3. Results
12.4. Conclusions
Acknowledgments
References
Chapter 13. Sensing and Computing with Liquid Marbles
13.1. Introduction
13.2. Collision-based Gate
13.3. Belousov–Zhabotinsky Cargo
13.4. Photosensor
13.5. Thermal Sensor
13.6. Robot Controller
13.7. Neuromorphic Marbles
13.8. Discussion
Acknowledgments
References
Chapter 14. Towards Colloidal Droplet Processors
14.1. Background
14.1.1. Data throughput
14.1.2. Heat dissipation
14.1.3. Energy consumption
14.2. Liquid Droplet Computer
14.2.1. Holonomic processors
14.3. Colloidal Processors
14.3.1. Phase change architectures
14.3.2. Microfluidic circuits
14.3.3. Layered shells
14.3.4. Granular media, foams, and plasmas
14.4. Biological Processors
14.5. Conclusions
Acknowledgment
References
Chapter 15. Biomolecular Motor-based Computing
15.1. Introduction
15.2. Applications of Biomolecular Motors in Computing
15.2.1. Parallel computing using biomolecular motors in nanofabricated networks
15.2.2. Computing using swarm robots prepared from biomolecular motors
15.2.2.1. Design and construction of molecular robots
15.2.2.2. Swarming of molecular robots
15.2.2.3. Controlling the shape morphology of swarms of molecular robots
15.2.2.4. Remote control of the swarming of molecular robots
15.2.2.5. Logical operation of molecular robots
15.2.2.6. Orthogonal swarming of molecular robots
15.3. Conclusions and Future Perspectives
References
Chapter 16. Computing with Square Electromagnetic Pulses
16.1. Introduction
16.2. Background
16.2.1. Brief historical retrospective
16.2.2. Basics of transmission line theory
16.3. Method
16.3.1. Main computing elements: Cross-points
16.3.2. Four-point crossing: Catt’s junction
16.3.3. Scattering matrix approach
16.3.4. Multi-way junctions: Series and parallel
16.3.5. Simulation results
16.3.6. Scaling down geometries
16.3.7. Pulse generation and control requirements
16.4. Future Directions
16.4.1. 3D-based structures
16.4.2. Graph-based computing
16.4.3. More complex signals and materials
16.5. Conclusion
Acknowledgements
References
Chapter 17. Creative Quantum Computing: Inverse FFT Sound Synthesis, Adaptive Sequencing and Musical Composition
17.1. Introduction
17.2. Why Quantum Computer Music?
17.3. Algorithmic Music
17.4. qSyn: Inverse FFT Sound Synthesis
17.5. qSeq: Adaptive Musical Sequencer
17.6. The Composition Zeno
17.7. Concluding Remarks
Appendix
Acknowledgments
References
Chapter 18. Logical Gates in Natural Erosion of Sandstone
18.1. Introduction
18.2. Modeling of Natural Erosion
18.3. Specific Parameters
18.4. Gates
18.4.1. AND gate
18.4.2. XOR gate
18.4.3. One-bit half-adder
18.5. Discussion
Supplementary Materials
References
Chapter 19. A Case of Toy Computing Implementing Digital Logics with “Minecraft”
19.1. Introduction
19.2. History and Theory of Toy Computing
19.3. Digital Logics in “Minecraft”
19.3.1. Signal generation and transportation
19.3.2. NAND gates
19.4. Digital Circuits in “Minecraft” and the Remains of Electronics
19.4.1. The circuit
19.4.2. The 4-bit full adder build with TTL-logic
19.4.3. The 4-bit full adder build in “Minecraft”
19.5. Project Discussion
19.5.1. Building a BCD decoder in “Minecraft”
19.5.2. The computational labyrinth
19.5.3. Walking the way of the signal
19.6. Summary
Chapter 20. Evolving Conductive Polymer Neural Networks on Wetware
20.1. Introduction
20.2. Introduction of Polymer Neural Networks
20.3. Electropolymerisation of Conducting Polymer Wire
20.3.1. Polymer wire growth
20.3.2. Wire diameter and growth rate
20.3.3. Conductance increase of wires
20.3.4. Directional growth of wire and 3D growth
20.4. Machine Learning for Polymer Wire Growth
20.4.1. Supervised learning: Simple perceptron for simple logic gates
20.4.2. Unsupervised learning: Autoencoder for feature extraction
20.5. Conclusions
References
Index