Demystifying Computation: A Hands-on Introduction

by Apostolos Syropoulos

Overview

Problem solving in computing is referred to as computational thinking. The theory behind this concept is challenging in its technicalities, yet simple in its ideas. This book introduces the theory of computation from its inception to current form of complexity; from explanations of how the field of computer science was formed using classical ideas in mathematics by Gödel, to conceptualization of the Turing Machine, to its more recent innovations in quantum computation, hypercomputation, vague computing and natural computing. It describes the impact of these in relation to academia, business and wider society, providing a sound theoretical basis for its practical application.Written for accessibility, Demystifying Computation provides the basic knowledge needed for non-experts in the field, undergraduate computer scientists and students of information and communication technology and software development.

Product Details

ISBN-13:	9781786342669
Publisher:	World Scientific Publishing Europe Ltd
Publication date:	06/01/2017
Pages:	216
Product dimensions:	5.90(w) x 9.00(h) x 0.50(d)

Table of Contents

Preface vii

Acknowledgments xi

About the Author xiii

Chapter 1 A Brief History of Computing 1

1.1 From Numbers to Calculating 1

1.2 Mechanical Calculating Devices 6

1.3 Modern Computers 13

1.4 The Future of Computing 18

Annotated Bibliography 20

Chapter 2 From Hilbert to Gödel to Turing 23

2.1 Hilbert's Dream 23

2.2 Hilbert's Nightmare 29

2.3 The λ-calculus 34

2.4 The Turing Machine 36

2.5 The Church-Turing Thesis 43

2.6 Easy and Difficult Problems 47

Annotated Bibliography 50

Chapter 3 Hypercomputation 53

3.1 On Problems and Their Solutions 53

3.2 Hypercomputation Explained 56

3.3 The Mind as a Hypercomputer 61

3.4 Turing Machines and Modern Computers 65

3.5 Quantum Computers and Hypercomputation 68

3.6 Closing Remarks 69

Annotated Bibliography 69

Chapter 4 Natural Computing 71

4.1 DNA Computing 71

4.1.1 A Non-technical and Brief Overview of DNA 71

4.1.2 Computing with DNA Molecules 73

4.1.3 DNA Computers 76

4.2 Cellular Computing 79

4.2.1 Membrane Computing 79

4.2.2 Amorphous Computing 84

4.2.3 Cellular Automata 85

4.3 Physarum Machines 87

4.4 Swarm Intelligence 90

4.5 Chaos Computing 93

4.6 Analog Computing 96

4.7 Artificial Neural Networks 102

Annotated Bibliography 106

Chapter 5 Quantum Computing 109

5.1 Probability Theory 109

5.2 A Summary of Calculus 111

5.3 A Quick Exploration of Quantum Mechanics 114

5.4 What Is Quantum Computer? 122

5.5 Cluster-State Quantum Computing 131

5.6 Topological Quantum Computing 136

5.7 Adiabatic Quantum Computing 144

5.8 Programmable Quantum Computers 147

5.9 What Can We Do With a Quantum Computer? 149

Annotated Bibliography 152

Chapter 6 Vague Computing 155

6.1 What is Vagueness? 155

6.2 Fuzzy Sets and Fuzzy Logic in a Nutshell 161

6.3 Fuzzy Computing 163

6.4 Rough Sets and Computing 167

6.5 Vagueness and Quantum Mechanics 170

Annotated Bibliography 172

Chapter 7 Physical Reality and Computation 173

7.1 The Universe as a Computer 173

7.2 Is Space-Time Discrete or Continuous? 179

7.3 Ultimate Computing Devices 183

Annotated Bibliography 184

Author Index 187

Subject Index 191