*Pierluigi Frisco*

- Published in print:
- 2009
- Published Online:
- September 2009
- ISBN:
- 9780199542864
- eISBN:
- 9780191715679
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199542864.001.0001
- Subject:
- Mathematics, Applied Mathematics, Mathematical Biology

How could we use living cells to perform computation? Would our definition of computation change as a consequence of this? Could such a cell-computer outperform digital computers? These are some of ...
More

How could we use living cells to perform computation? Would our definition of computation change as a consequence of this? Could such a cell-computer outperform digital computers? These are some of the questions that the study of Membrane Computing tries to answer and are at the base of what is treated by this monograph. Descriptional and computational complexity of models in Membrane Computing are the two lines of research on which is the focus here. In this context this book reports the results of only some of the models present in this framework. The models considered here represent a very relevant part of all the models introduced so far in the study of Membrane Computing. They are in between the most studied models in the field and they cover a broad range of features (using symbol objects or string objects, based only on communications, inspired by intra- and intercellular processes, having or not having a tree as underlying structure, etc.) that gives a grasp of the enormous flexibility of this framework. Links with biology and Petri nets are constant through this book. This book aims also to inspire research. This book gives suggestions for research of various levels of difficulty and this book clearly indicates their importance and the relevance of the possible outcomes. Readers new to this field of research will find the provided examples particularly useful in the understanding of the treated topics.Less

How could we use living cells to perform computation? Would our definition of *computation* change as a consequence of this? Could such a cell-computer outperform digital computers? These are some of the questions that the study of *Membrane Computing* tries to answer and are at the base of what is treated by this monograph. Descriptional and computational complexity of models in Membrane Computing are the two lines of research on which is the focus here. In this context this book reports the results of only *some* of the models present in this framework. The models considered here represent a very relevant part of all the models introduced so far in the study of Membrane Computing. They are in between the most studied models in the field and they cover a broad range of features (using symbol objects or string objects, based only on communications, inspired by intra- and intercellular processes, having or not having a tree as underlying structure, etc.) that gives a grasp of the enormous flexibility of this framework. Links with biology and Petri nets are constant through this book. This book aims also to inspire research. This book gives suggestions for research of various levels of difficulty and this book clearly indicates their importance and the relevance of the possible outcomes. Readers new to this field of research will find the provided examples particularly useful in the understanding of the treated topics.

*Jack Copeland*

- Published in print:
- 2017
- Published Online:
- November 2020
- ISBN:
- 9780198747826
- eISBN:
- 9780191916946
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198747826.003.0014
- Subject:
- Computer Science, History of Computer Science

In 1936 mathematics was changing profoundly, thanks to Turing and his fellow revolutionaries Gödel and Church. Older views about the nature of mathematics, ...
More

In 1936 mathematics was changing profoundly, thanks to Turing and his fellow revolutionaries Gödel and Church. Older views about the nature of mathematics, such as those powerfully advocated by the great mathematician David Hilbert, were being swept away, and simultaneously the foundations for the modern computer era were being laid. These three revolutionaries were also catching the first glimpses of an exciting new world—the hitherto unknown and unimagined mathematical territory that lies beyond the computable. In the 1930s a group of iconoclastic mathematicians and logicians launched the field that we now call theoretical computer science. These pioneers embarked on an investigation to spell out the meaning and limits of computation. Pre-eminent among them were Alan Turing, Kurt Gödel, and Alonzo Church. These three men are pivotal figures in the story of modern science, and it is probably true to say that, even today, their role in the history of science is underappreciated. The theoretical work that they carried out in the 1930s laid the foundations for the computer revolution, and the computer revolution in turn fuelled the rocketing expansion of scientific knowledge that characterizes modern times. Previously undreamed of number-crunching power was soon boosting all fields of scientific enquiry, thanks in large part to these seminal investigations. Yet, at the time, Turing, Gödel, and Church would have thought of themselves as working in a most abstract field, far flung from practical computing. Their concern was with the very foundations of mathematics. Kurt Gödel (Fig. 7.1), a taciturn 25-year-old mathematician from Vienna University, ushered in a new era in mathematics with his 1931 theorem that arithmetic is incomplete. In a sentence, what Gödel showed is that more is true in mathematics than can be formally proved. This sensational result shocked, and even angered, some mathematicians. It was thought that everything that matters ought to be provable, because only rigorous proof by transparent and obvious rules brings certainty.
Less

In 1936 mathematics was changing profoundly, thanks to Turing and his fellow revolutionaries Gödel and Church. Older views about the nature of mathematics, such as those powerfully advocated by the great mathematician David Hilbert, were being swept away, and simultaneously the foundations for the modern computer era were being laid. These three revolutionaries were also catching the first glimpses of an exciting new world—the hitherto unknown and unimagined mathematical territory that lies beyond the computable. In the 1930s a group of iconoclastic mathematicians and logicians launched the field that we now call theoretical computer science. These pioneers embarked on an investigation to spell out the meaning and limits of computation. Pre-eminent among them were Alan Turing, Kurt Gödel, and Alonzo Church. These three men are pivotal figures in the story of modern science, and it is probably true to say that, even today, their role in the history of science is underappreciated. The theoretical work that they carried out in the 1930s laid the foundations for the computer revolution, and the computer revolution in turn fuelled the rocketing expansion of scientific knowledge that characterizes modern times. Previously undreamed of number-crunching power was soon boosting all fields of scientific enquiry, thanks in large part to these seminal investigations. Yet, at the time, Turing, Gödel, and Church would have thought of themselves as working in a most abstract field, far flung from practical computing. Their concern was with the very foundations of mathematics. Kurt Gödel (Fig. 7.1), a taciturn 25-year-old mathematician from Vienna University, ushered in a new era in mathematics with his 1931 theorem that arithmetic is incomplete. In a sentence, what Gödel showed is that more is true in mathematics than can be formally proved. This sensational result shocked, and even angered, some mathematicians. It was thought that everything that matters ought to be provable, because only rigorous proof by transparent and obvious rules brings certainty.

*Jack Copeland*

- Published in print:
- 2017
- Published Online:
- November 2020
- ISBN:
- 9780198747826
- eISBN:
- 9780191916946
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780198747826.003.0013
- Subject:
- Computer Science, History of Computer Science

There is no such person as the inventor of the computer: it was a group effort. The many pioneers involved worked in different places and at different ...
More

There is no such person as the inventor of the computer: it was a group effort. The many pioneers involved worked in different places and at different times, some in relative isolation and others within collaborative research networks. There are some very famous names among them, such as Charles Babbage and John von Neumann—and, of course, Alan Turing himself. Other leading names in this roll of honour include Konrad Zuse, Tommy Flowers, Howard Aiken, John Atanasoff, John Mauchly, Presper Eckert, Jay Forrester, Harry Huskey, Julian Bigelow, Samuel Alexander, Ralph Slutz, Trevor Pearcey, Maurice Wilkes, Max Newman, Freddie Williams, and Tom Kilburn. Turing’s own outstanding contribution was to invent what he called the ‘universal computing machine’. He was first to describe the basic logical principles of the modern computer, writing these down in 1936, 12 years before the appearance of the earliest implementation of his ideas. This came in 1948, when Williams and Kilburn succeeded in wiring together the first electronic universal computing machine—the first modern electronic computer. In 1936, at the age of just 23, Turing invented the fundamental logical principles of the modern computer—almost by accident. A shy boyish-looking genius, he had recently been elected a Fellow of King’s College, Cambridge. The young Turing worked alone, in a spartan room at the top of an ancient stone building beside the River Cam. It was all quite the opposite of a modern research facility—Cambridge’s scholars had been doing their thinking in comfortless stone buildings, reminiscent of cathedrals or monasteries, ever since the university had begun to thrive in the Middle Ages. A few steps from King’s, along narrow medieval lanes, are the buildings and courtyards where, in the seventeenth century, Isaac Newton revolutionized our understanding of the universe. Turing was about to usher in another revolution. He was engaged in theoretical work in the foundations of mathematics. No-one could have guessed that anything of practical value would emerge from his highly abstract research, let alone a machine that would change all our lives.
Less

There is no such person as the inventor of the computer: it was a group effort. The many pioneers involved worked in different places and at different times, some in relative isolation and others within collaborative research networks. There are some very famous names among them, such as Charles Babbage and John von Neumann—and, of course, Alan Turing himself. Other leading names in this roll of honour include Konrad Zuse, Tommy Flowers, Howard Aiken, John Atanasoff, John Mauchly, Presper Eckert, Jay Forrester, Harry Huskey, Julian Bigelow, Samuel Alexander, Ralph Slutz, Trevor Pearcey, Maurice Wilkes, Max Newman, Freddie Williams, and Tom Kilburn. Turing’s own outstanding contribution was to invent what he called the ‘universal computing machine’. He was first to describe the basic logical principles of the modern computer, writing these down in 1936, 12 years before the appearance of the earliest implementation of his ideas. This came in 1948, when Williams and Kilburn succeeded in wiring together the first electronic universal computing machine—the first modern electronic computer. In 1936, at the age of just 23, Turing invented the fundamental logical principles of the modern computer—almost by accident. A shy boyish-looking genius, he had recently been elected a Fellow of King’s College, Cambridge. The young Turing worked alone, in a spartan room at the top of an ancient stone building beside the River Cam. It was all quite the opposite of a modern research facility—Cambridge’s scholars had been doing their thinking in comfortless stone buildings, reminiscent of cathedrals or monasteries, ever since the university had begun to thrive in the Middle Ages. A few steps from King’s, along narrow medieval lanes, are the buildings and courtyards where, in the seventeenth century, Isaac Newton revolutionized our understanding of the universe. Turing was about to usher in another revolution. He was engaged in theoretical work in the foundations of mathematics. No-one could have guessed that anything of practical value would emerge from his highly abstract research, let alone a machine that would change all our lives.

*Cristopher Moore and Stephan Mertens*

- Published in print:
- 2011
- Published Online:
- December 2013
- ISBN:
- 9780199233212
- eISBN:
- 9780191775079
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199233212.001.0001
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics

Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often ...
More

Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. It starts with a lucid explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. It then leads the reader through the complexity of mazes and games; optimisation in theory and practice; randomised algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, it uses a minimum of formalism, providing explanations that are both deep and accessible.Less

Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. It starts with a lucid explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. It then leads the reader through the complexity of mazes and games; optimisation in theory and practice; randomised algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, it uses a minimum of formalism, providing explanations that are both deep and accessible.