In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing's Vision, Chris Bernhardt explains the theory, Turing's most important contribution, for the In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing's Vision, Chris Bernhardt explains the theory, Turing's most important contribution, for the general reader. Bernhardt argues that the strength of Turing's theory is its simplicity, and that, explained in a straightforward manner, it is eminently understandable by the nonspecialist. As Marvin Minsky writes, -The sheer simplicity of the theory's foundation and extraordinary short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory.- Bernhardt begins with the foundation and systematically builds to the surprising conclusions. He also views Turing's theory in the context of mathematical history, other views of computation (including those of Alonzo Church), Turing's later work, and the birth of the modern computer. In the paper, -On Computable Numbers, with an Application to the Entscheidungsproblem, - Turing thinks carefully about how humans perform computation, breaking it down into a sequence of steps, and then constructs theoretical machines capable of performing each step. Turing wanted to show that there were problems that were beyond any computer's ability to solve; in particular, he wanted to find a decision problem that he could prove was undecidable. To explain Turing's ideas, Bernhardt examines three well-known decision problems to explore the concept of undecidability; investigates theoretical computing machines, including Turing machines; explains universal machines; and proves that certain problems are undecidable, including Turing's problem concerning computable numbers.

# Turing's Vision: The Birth of Computer Science

In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing's Vision, Chris Bernhardt explains the theory, Turing's most important contribution, for the In 1936, when he was just twenty-four years old, Alan Turing wrote a remarkable paper in which he outlined the theory of computation, laying out the ideas that underlie all modern computers. This groundbreaking and powerful theory now forms the basis of computer science. In Turing's Vision, Chris Bernhardt explains the theory, Turing's most important contribution, for the general reader. Bernhardt argues that the strength of Turing's theory is its simplicity, and that, explained in a straightforward manner, it is eminently understandable by the nonspecialist. As Marvin Minsky writes, -The sheer simplicity of the theory's foundation and extraordinary short path from this foundation to its logical and surprising conclusions give the theory a mathematical beauty that alone guarantees it a permanent place in computer theory.- Bernhardt begins with the foundation and systematically builds to the surprising conclusions. He also views Turing's theory in the context of mathematical history, other views of computation (including those of Alonzo Church), Turing's later work, and the birth of the modern computer. In the paper, -On Computable Numbers, with an Application to the Entscheidungsproblem, - Turing thinks carefully about how humans perform computation, breaking it down into a sequence of steps, and then constructs theoretical machines capable of performing each step. Turing wanted to show that there were problems that were beyond any computer's ability to solve; in particular, he wanted to find a decision problem that he could prove was undecidable. To explain Turing's ideas, Bernhardt examines three well-known decision problems to explore the concept of undecidability; investigates theoretical computing machines, including Turing machines; explains universal machines; and proves that certain problems are undecidable, including Turing's problem concerning computable numbers.

Compare

5out of 5Steve–This book breaks down Turing's approach to computation, and in doing so gives a glimpse into what "universal computers" really are. I believe this book should be required reading in any high-school math class, anyone who is wondering if computer science is right for them, of anyone wondering why some problems are easy for computers while others are hard. This is written for a regular person, not a computer scientist. There's a bit of logical reasoning and even some counting! in the book, but not This book breaks down Turing's approach to computation, and in doing so gives a glimpse into what "universal computers" really are. I believe this book should be required reading in any high-school math class, anyone who is wondering if computer science is right for them, of anyone wondering why some problems are easy for computers while others are hard. This is written for a regular person, not a computer scientist. There's a bit of logical reasoning and even some counting! in the book, but nothing that should overcome someone who wants to learn what computation is all about. The author sets out to explain Turing's historic paper: "On Computable Numbers, with an Application to the Entscheidungsproblem". I know, I know, I probably don't need to say any more than that - you're already ordering it off of Amazon. Or, more likely, you're like most of the rest of the world and couldn't care less about some stuffy old paper with a German word in the title. This paper is one well worth being familiar with: it sparked the computing revolution. No, the paper didn't describe how to build a computer, or the internet, it instead showed a way to capture how problems can be approached and solved systematically, and that not all problems have answers that can be computed. That last statement might seem obvious to you, but it wasn't to mathematicians around Turing's time. Many were of the opinion that any problem that could be expressed could be solved, and it was just a matter of time before a proof was developed to show that this was the case universally. Turing went after the "decision problem" or Entscheidungsproblem variant: prove that any mathematical statement is either true or false. Turing showed that there is a third option: that some problems are undecidable; a true or false decision cannot be reached no matter how long you (or a similarly capable computer) try to compute the answer. This is not the most straight-forward concept to understand, and yet the author lays out a series of brief chapters that works a reader into position to discover this fact for themselves. The author does better than to try to go through Turing's paper section by section, he goes through the quintessential ideas and arguments that Turing used to prove his point. He wisely includes more recent explanations and examples where appropriate, and these anachronisms greatly improve readability. The author also elected to tie the mathematical results in with the birth of the modern computing age, but sticks just to the first few years of actualized computers, and also gives a thoughtful account of Turing's final years. There are other interesting books about Turing's life and legacy, a bunch related to his time breaking the German Enigma code in WWII, but this the best one I've seen to date that really tries to tackle his core mathematical contribution. To be completely fair, this is not a new subject for me. I first learned about Turing machines in my undergraduate days, and I've spent a good amount of time reading about computability and related topics. That said, I wish I had read this book before my automata theory textbook because it does such a great job with the subject. It's no replacement for a proper textbook if you're aiming to be a computer scientist - I believe getting a real feel for computability and undecidable problems requires spending time building examples of deterministic finite automata, context free grammars, and the like - but this book really gets the reader into the right frame of mind to do that sort of thinking. Two minor improvements for the book: 1. The term algorithm is used in the introduction, but it's not clearly defined. I think adding the word to a sentence a few back from where it is first seen should clear up any confusion: "He realizes that any computation can be broken down to a sequence of simple steps, *called an algorithm*." It might not be the most rigorous definition of the term, but functionally I think it works. 2. Typo on page 84: There's an equation that translates a binary number into a decimal one - but an exponent of 7 is used where a 6 should be: Printed: 1 x 2^7 + 0 x 2^7 + 0 x 2^5 ... Correct: 1 x 2^7 + 0 x 2^6 + 0 x 2^5 ... It doesn't change the result, but if a reader is unfamiliar with different number systems it might be a little confusing.

5out of 5Jersey–Damn this book was good. I wish I read it while I took Introduction to Complexity Theory in college. Bernhardt explains some pretty challenging concepts in a very digestible way. On top of that, Bernhardt gives a great history lesson and helps you appreciate why these seemingly esoteric ideas are so important so impactful

4out of 5Igor Sedlár–An excellent short and mostly informal introduction to the theory if computation and related topics, with some historical background material. Highly recommended to students but an interesting read for specialists as well. The text was not edited carefully, though, as it contains a number of typos, double words or superfluous words.

5out of 5Andreea–“We shall do a much better programming job, provided we approach the task with a full appreciation of its tremendous difficulty, provided that we respect the intrinsic limitations of the human mind and approach the task as very humble programmers.” - Alan Turing

5out of 5Pogo–Oof. My 2 star rating should not necessarily be regarded as me saying that this book is “bad”… just not what I was expecting. I had hoped for a more broader, general-interest and abstract overview of the concepts, rather than such nitty gritty details. I’m grateful that the world is populated with those who find such dry and demanding thought enjoyable, because it has changed life as we know it dramatically, but for me finishing this book was a matter of stubbornness, an exercise in self-discipl Oof. My 2 star rating should not necessarily be regarded as me saying that this book is “bad”… just not what I was expecting. I had hoped for a more broader, general-interest and abstract overview of the concepts, rather than such nitty gritty details. I’m grateful that the world is populated with those who find such dry and demanding thought enjoyable, because it has changed life as we know it dramatically, but for me finishing this book was a matter of stubbornness, an exercise in self-discipline, and a little masochism thrown in.

5out of 5Khan Ashraf Alif–Unnecessarily sophisticated

5out of 5Jess Sohn–I failed this book. Despite my sincere interest in math, logic, and Turing, I was not able to get the most out of Bernhardt's deftly written explanation of Turing's all important thesis. I am not ashamed to say that a smarter person or a more dedicated reader than myself, particularly in the field of math or logic or computer science, will probably fly through this. I have great respect for Bernhardt's commitment to translating this dense subject for a person who is unfamiliar with the field. Ho I failed this book. Despite my sincere interest in math, logic, and Turing, I was not able to get the most out of Bernhardt's deftly written explanation of Turing's all important thesis. I am not ashamed to say that a smarter person or a more dedicated reader than myself, particularly in the field of math or logic or computer science, will probably fly through this. I have great respect for Bernhardt's commitment to translating this dense subject for a person who is unfamiliar with the field. However, this book deserved more of my attention, as I occasionally grabbed pencil and paper to bravely attempt to follow the method to the Turing machine madness, or more often, ignored it entirely for months. But even for a dumb dummy like myself, I did thoroughly enjoy the last section on Turing's Legacy, which speaks loudly even for those who are unable to grasp the nuances of his logic and intellect. Turing's innovation, influence, and ripple effect are undeniable. I shall direct any interested, intelligent readers towards this much better review.

4out of 5Allan Olley–This is an interesting introduction to some of the key mathematical work of Alan Turing (mostly his 1936 results on Computable Numbers and Turing Machines) relating it to both contemporary developments in logic (the lambda calculus) and later developments in computer science and related ideas like finite automata. The book is thus mostly an introduction to mathematical and computer science concepts but serves to give them some intellectual context also and even a little bit of social context for This is an interesting introduction to some of the key mathematical work of Alan Turing (mostly his 1936 results on Computable Numbers and Turing Machines) relating it to both contemporary developments in logic (the lambda calculus) and later developments in computer science and related ideas like finite automata. The book is thus mostly an introduction to mathematical and computer science concepts but serves to give them some intellectual context also and even a little bit of social context for Turing's life and legacy. The book begins with some discussion of mathematical logic, Hilbert's program (the Entscheidungsproblem) and the Godel results that Turing's work built on, responded and contributed to. Things like finite automata and the lambda calculus are worked though in preparation to lead the reader through Turing's laying out of his model of computing in terms of Turing machines and proof that the computable numbers are not effectively innumerable. Also other mathematical work such as Cantor's diagonalization argument are sketched out and worked through to the extent necessary to relate them to Turing's work. Some key elements of Turing's life and other work are summarized as are a few seminal instances from the origin of the computer, some philosophical issues around artificial intelligence and a final reflection on Turing's life and legacy. The book is a fairly readable and understandable exposition of the mathematics. However at times I found the examples and work through of the problems a bit brief. I had some rather haphazard knowledge of the mathematics in Turing's work including my own attempt to read Turing's paper, but much of the mathematical logic and machine theory was new to me. There is a difficult balance between being comprehensible to the general reader (or at least the interested neophyte) and avoiding tedium in explaining the very simple but elaborate procedures involved. Also the depth and breadth of the discussion is limited. Careful reading would no doubt be rewarded with greater comprehension but I found I profitably read it without having to master all the technical nuance presented. The history presented is often very schematic outside of tracing the pedigree of certain mathematical techniques there are just a few bits of greatest hits. The reader may come away with a somewhat inflated sense of Turing's role in the origin of actual computing machines (Turing's exact contributions to various elements is a matter of some dispute), a few interesting early machines are left unmentioned in the cursory round up of early computers but otherwise I did not notice any serious errors.

5out of 5D. Rogers–Bernhardt provides a brilliant overview of Alan Turing's most groundbreaking contributions. The only prerequisites for this read are reasoning skills and familiarity with mathematical notation (if you know '>' is the greater-than sign and that {a,b,c} is a set, you're golden). The book gradually builds on itself, starting with logic and ending with the core ideas of Turing's revered paper. A clear explanation of the overall goals of early 20th century mathematicians is provided as well. So, by th Bernhardt provides a brilliant overview of Alan Turing's most groundbreaking contributions. The only prerequisites for this read are reasoning skills and familiarity with mathematical notation (if you know '>' is the greater-than sign and that {a,b,c} is a set, you're golden). The book gradually builds on itself, starting with logic and ending with the core ideas of Turing's revered paper. A clear explanation of the overall goals of early 20th century mathematicians is provided as well. So, by the last page, not only do you come out with a solid understanding of Turing's ideas but also the context and motivations of his work. If you've read and enjoyed "Godel's Proof" by Nagel and Newman, you'll enjoy this. Conversely, if you've already read this and are looking for something similar, look no further than "Godel's Proof"!

4out of 5Pranav–Excellent primer for curious people, who do not have a technical background, to know about who Alan Turing was and what his contribution was to the modern technical landscape. We owe a great debt to his genius for inventing the "theoretical computers" which he called the "universal machines" which started the genesis of all modern computing devices; almost every gadget in sight, our computers, phones and other digital systems. Most people know Alan Turing as the code-breaker, who shorted the WWII Excellent primer for curious people, who do not have a technical background, to know about who Alan Turing was and what his contribution was to the modern technical landscape. We owe a great debt to his genius for inventing the "theoretical computers" which he called the "universal machines" which started the genesis of all modern computing devices; almost every gadget in sight, our computers, phones and other digital systems. Most people know Alan Turing as the code-breaker, who shorted the WWII and saved countless lives by cracking open Enigma encryption used by Nazi Germany. However few know that it was Alan Turing who pioneered the field of computer science. This book gives an account of how and why!

5out of 5Frank–Bernhardt does an admirable job of demonstrating and explaining the huge contributions Alan Turing made to both mathematics (especially set and number theory) and the foundation of what we now call computer science. The math and logic are not particularly “difficult” to understand, but I hadn’t encountered much of the notation (sets especially) and thinking (mathematical proofs) since high school math class. The implications of Turing’s logical mathematical arguments are stunning, especially as Bernhardt does an admirable job of demonstrating and explaining the huge contributions Alan Turing made to both mathematics (especially set and number theory) and the foundation of what we now call computer science. The math and logic are not particularly “difficult” to understand, but I hadn’t encountered much of the notation (sets especially) and thinking (mathematical proofs) since high school math class. The implications of Turing’s logical mathematical arguments are stunning, especially as they relate to computer programming and calculation. Beware, this is a bit of a slow read due to lots of math!

4out of 5Cole–Wow I wish I had this book when I took my Theory of Computation course. My prior experience made the content easier to follow, but there is a considerable amount of auxiliary information which is sometimes difficult to distinguish from the essential information. The author seems to propose as his thesis that he will be explaining Turing's ground breaking paper, providing all the necessary background information (and more). With the side-topics and the cumulative nature of the background informat Wow I wish I had this book when I took my Theory of Computation course. My prior experience made the content easier to follow, but there is a considerable amount of auxiliary information which is sometimes difficult to distinguish from the essential information. The author seems to propose as his thesis that he will be explaining Turing's ground breaking paper, providing all the necessary background information (and more). With the side-topics and the cumulative nature of the background information, I feel like the author should have reinstated and summarized the content. Without such a summary, I was left at the end of chapter 8 thinking "oh, we're done?"

4out of 5Marlene–Bernhardt did a great job of providing a great overview of computational theory, specifically the vast influence that Turing had on the field. I particularly enjoyed the way certain proofs were explained using easy to understand examples, before the official proof was introduced. I also enjoyed the asides throughout the whole book. That being said, I do have a CS background, and do not think I would have been able as nicely without it. But given the difficulty of the topic, Bernhardt does a fanta Bernhardt did a great job of providing a great overview of computational theory, specifically the vast influence that Turing had on the field. I particularly enjoyed the way certain proofs were explained using easy to understand examples, before the official proof was introduced. I also enjoyed the asides throughout the whole book. That being said, I do have a CS background, and do not think I would have been able as nicely without it. But given the difficulty of the topic, Bernhardt does a fantastic job!

5out of 5Shozab Qasim–This book will give immense pleasure to anyone interested in the field of Theoretical Computer Science. With a brief introduction with regards to the works of mathematical logic by Russell, Hilbert and Godel, then moving on to topics such as finite automata, Turing machines, undecidable problems and finally countable numbers, this book provides a remarkable introduction to the methods employed by Turing to answer the question of the Entscheidungsproblem.

4out of 5Peter Corke–I knew a lot of the Bletchley history and had read the imitation game paper, but never read the computable numbers paper. This book covers that in a very accessible way for a non computer scientist. Turing machines, encodings and the halting problem.

5out of 5Tom Zollo–This seems to be a very underrated book. Besides Godel Escher Bach, this book gave me more insight into what computing really is than any other I've come across, and I'd strongly suggest it to anyone entering the field. This seems to be a very underrated book. Besides Godel Escher Bach, this book gave me more insight into what computing really is than any other I've come across, and I'd strongly suggest it to anyone entering the field.

4out of 5Shawn Aebi–Much of the book is unreadable for someone without an advanced degree. The historical anecdotes are sporadically interspersed and helpful but the magnitude of Turing's impact is not truly felt. Much of the book is unreadable for someone without an advanced degree. The historical anecdotes are sporadically interspersed and helpful but the magnitude of Turing's impact is not truly felt.

5out of 5Kadir Korkmaz–This review has been hidden because it contains spoilers. To view it, click here. It is a good book to understand main ideas related to computing. I have learned a lot from this book. After this book again I have remembered the importance of reading.

5out of 5Alon Cohen–Superb. A fabulous introduction to Theory of Computation. As Turing elegantly laid the foundations of Computer Science, Bernhardt elegantly explains those foundations. Highly recommend

5out of 5Erika–3 stars because i wanted more in depth info on hid life not what i learn in class. but this would be a great review

4out of 5Gowtham Kaki–A remarkably lucid (yet sufficiently rigorous) commentary on Turing’s landmark 1936 paper that introduced computing machines. This book helped me finally internalize Turing’s insights.

4out of 5Matthew–Wonderful intro to Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem.

4out of 5Cameron E. Wild–If you ever wanted to have in insight into pure genius, this book is for you.

4out of 5Hassaan Naeem–Although a difficult read to parse at times, given the multitude of mathematical concepts and proofs, well worth the read!

4out of 5Kevin–Very enjoyable for the layperson!

5out of 5Nick Ziegler–This book contains many wonderful proofs; for example, proof that I will never understand computer science or most mathematics beyond high school level. However, I was grateful for this brief and generous opportunity to stand on the threshold of the subjects and, if not understand, at least gain some familiarity. The prose reads like it was written by a mathematician, which it was; and the historical portions are not very good, by history standards. But the unadorned and telegraphic style is wha This book contains many wonderful proofs; for example, proof that I will never understand computer science or most mathematics beyond high school level. However, I was grateful for this brief and generous opportunity to stand on the threshold of the subjects and, if not understand, at least gain some familiarity. The prose reads like it was written by a mathematician, which it was; and the historical portions are not very good, by history standards. But the unadorned and telegraphic style is what makes it approachable, and for the book's purposes they count as virtues. I now feel I can approach works in the history of mathematics and computing, and perhaps asymptotically approach understanding (which, as I've pointed out, will never be mine).

5out of 5Diego Quintana–I don't usually write reviews about books, but as a CS enthusiast I've been trying to wrap my head around turing machines for a while, and well, this book explain things beautifully. The writing feels like I'm reading at lecture notes, and it makes me feel like I'm looking at the development of something beautiful at the same time. The explanations in the book are not purely demonstrative (it has lots of demonstrations by contradiction, which made them more intuitive in my opinion), but rather a I don't usually write reviews about books, but as a CS enthusiast I've been trying to wrap my head around turing machines for a while, and well, this book explain things beautifully. The writing feels like I'm reading at lecture notes, and it makes me feel like I'm looking at the development of something beautiful at the same time. The explanations in the book are not purely demonstrative (it has lots of demonstrations by contradiction, which made them more intuitive in my opinion), but rather aim to _explain_ things, i.e. putting things in a mathematical and historical context. I can't recommend this book enough.

4out of 5BCS–Alan Turing is a much known and celebrated figure in the world of computing. He is credited as being one of the founding fathers of computer science. Many will know of him from the famous Turing test which attempts to assess a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human. Turing's most important intellectual work is his paper ‘On Computable Numbers, with an Application to the Entscheidungs problem’, published in 1936. If you've ever Alan Turing is a much known and celebrated figure in the world of computing. He is credited as being one of the founding fathers of computer science. Many will know of him from the famous Turing test which attempts to assess a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human. Turing's most important intellectual work is his paper ‘On Computable Numbers, with an Application to the Entscheidungs problem’, published in 1936. If you've ever attempted to read it, you would be forgiven for being left with a feeling that you've not fully appreciated its value. Where as other books might take a holistic view of Turing’s life and works, this book seeks to describe the background and explain the value of the ideas contained in his most famous publication. Across 8 well defined chapters it covers the history of mathematics, theoretical computing machines, Turing machines, as well as alternative ways of looking at computation including lambda calculus, the tag system and cellular automata. The book builds to provide a ground-up explanation of how Turing developed his ideas and why they still remain important to the field of computer science to this day. The book ends with a fairly short chapter describing Turing's career and how his ideas contributed to the production of the first computers from the 1940s onwards. Although the book is predominantly about his work rather than his life, It also goes on to suggest that his death in 1954 may have been an accident rather than suicide. The book ends with Gordon Brown’s 2003 apology for his treatment at a time when attitudes towards homosexuality were very different to how they are today. The book is not designed with a ‘mathematician readership’ in mind, and I was generally impressed by its accessibility. The use of examples such as the Barber paradox as an example of proof by contradiction and Hilbert’s Hotel to explain cardinality greatly helped to explain the ideas in the book, although I did find myself rereading sections at times to ensure I had a full understanding. This book is good value for money and recommended reading for anyone interested in improving their understanding of the origin of many of the fundamentals we all now take for granted in the fast-moving field of computer science. Review by Dean Burnell MBCS Originally posted: http://www.bcs.org/content/conWebDoc/...

5out of 5Liam–"Kleene showed that any given regular expression you can design a finite automaton to accept just the strings defined by the expression. He also showed the converse that, given any finite automaton, the strings that it accepts can be described by a regular expression. In this sense, we can describe regular expressions and finite automata as equivalent. They both describe exactly the same set of strings." (39) "Anything that can be computed can be computed by a Turing machine." (62) "'A man provide "Kleene showed that any given regular expression you can design a finite automaton to accept just the strings defined by the expression. He also showed the converse that, given any finite automaton, the strings that it accepts can be described by a regular expression. In this sense, we can describe regular expressions and finite automata as equivalent. They both describe exactly the same set of strings." (39) "Anything that can be computed can be computed by a Turing machine." (62) "'A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine.'" (quoting Turing, 87) "Turing had proved one of the greatest mathematicians wrong. However, the real genius was in the method. His theoretical machines that were simple to understand and yet, as he showed, capable of doing any computation. His argument showed the existence of the universal computer and then showed its power and its limits." (145)

4out of 5Volodymyr–In which it is shown to us why do we need science — how approaching what would seems to be a pure scientific, yet fundamental problem yields practical application on which our modern civilization relies on. And what is the genius of Alan Turing — who solved this problem and used results of this work for a practical application. Perfect concise historical and mathematical overview of computational theory and Turing’s contribution.