Understanding computation

Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you'll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programmi...

Full description

Bibliographic Details
Main Author: Stuart, Tom
Format: eBook
Language:English
Published: Sebastopol, CA O'Reilly Media 2013
Subjects:
Online Access:
Collection: O'Reilly - Collection details see MPG.ReNa
LEADER 05686nmm a2200481 u 4500
001 EB001952754
003 EBX01000000000000001115656
005 00000000000000.0
007 cr|||||||||||||||||||||
008 210123 ||| eng
020 |a 9781449330101 
020 |a 144933010X 
020 |a 1449329276 
020 |a 9781449329273 
020 |a 9781449330118 
050 4 |a QA76 
100 1 |a Stuart, Tom 
245 0 0 |a Understanding computation  |c Tom Stuart 
260 |a Sebastopol, CA  |b O'Reilly Media  |c 2013 
300 |a 1 volume  |b illustrations 
505 0 |a Regular Expressions -- Syntax -- Semantics -- Parsing -- Equivalence -- 4. Just Add Power -- Deterministic Pushdown Automata -- Storage -- Rules -- Determinism -- Simulation -- Nondeterministic Pushdown Automata -- Simulation -- Nonequivalence -- Parsing with Pushdown Automata -- Lexical Analysis -- Syntactic Analysis -- Practicalities -- How Much Power? -- 5. The Ultimate Machine -- Deterministic Turing Machines -- Storage -- Rules -- Determinism -- Simulation -- Nondeterministic Turing Machines -- Maximum Power -- Internal Storage -- Subroutines -- Multiple Tapes -- Multidimensional Tape -- General-Purpose Machines -- Encoding -- Simulation -- pt. II Computation and Computability -- 6. Programming with Nothing -- Impersonating the Lambda Calculus -- Working with Procs -- The Problem -- Numbers -- Booleans -- Predicates -- Pairs -- Numeric Operations -- Lists -- Strings -- The Solution -- Advanced Programming Techniques -- Implementing the Lambda Calculus -- Syntax -- Semantics --  
505 0 |a Machine generated contents note: 1. Just Enough Ruby -- Interactive Ruby Shell -- Values -- Basic Data -- Data Structures -- Procs -- Control Flow -- Objects and Methods -- Classes and Modules -- Miscellaneous Features -- Local Variables and Assignment -- String Interpolation -- Inspecting Objects -- Printing Strings -- Variadic Methods -- Blocks -- Enumerable -- Struct -- Monkey Patching -- Defining Constants -- Removing Constants -- pt. I Programs and Machines -- 2. The Meaning of Programs -- The Meaning of "Meaning" -- Syntax -- Operational Semantics -- Small-Step Semantics -- Big-Step Semantics -- Denotational Semantics -- Expressions -- Statements -- Applications -- Formal Semantics in Practice -- Formality -- Finding Meaning -- Alternatives -- Implementing Parsers -- 3. The Simplest Computers -- Deterministic Finite Automata -- States, Rules, and Input -- Output -- Determinism -- Simulation -- Nondeterministic Finite Automata -- Nondeterminism -- Free Moves --  
505 0 |a Parsing -- 7. Universality Is Everywhere -- Lambda Calculus -- Partial Recursive Functions -- SKI Combinator Calculus -- Iota -- Tag Systems -- Cyclic Tag Systems -- Conway's Game of Life -- Rule 110 -- Wolfram's 2,3 Turing Machine -- 8. Impossible Programs -- The Facts of Life -- Universal Systems Can Perform Algorithms -- Programs Can Stand In for Turing Machines -- Code Is Data -- Universal Systems Can Loop Forever -- Programs Can Refer to Themselves -- Decidability -- The Halting Problem -- Building a Halting Checker -- It'll Never Work -- Other Undecidable Problems -- Depressing Implications -- Why Does This Happen? -- Coping with Uncomputability -- 9. Programming in Toyland -- Abstract Interpretation -- Route Planning -- Abstraction: Multiplying Signs -- Safety and Approximation: Adding Signs -- Static Semantics -- Implementation -- Benefits and Limitations -- Applications 
653 |a Complexité de calcul (Informatique) 
653 |a Mathematics / Data processing / http://id.loc.gov/authorities/subjects/sh85082146 
653 |a Mathematics / Data processing / fast 
653 |a Mathématiques / Informatique 
653 |a Computer science / http://id.loc.gov/authorities/subjects/sh89003285 
653 |a Computer science / fast 
653 |a Electronic Data Processing 
653 |a Programming languages (Electronic computers) / bisacsh 
653 |a Informatique 
653 |a Computational complexity / http://id.loc.gov/authorities/subjects/sh85029473 
653 |a Computational complexity / fast 
041 0 7 |a eng  |2 ISO 639-2 
989 |b OREILLY  |a O'Reilly 
776 |z 9781449330118 
776 |z 9781449329273 
856 4 0 |u https://learning.oreilly.com/library/view/~/9781449330071/?ar  |x Verlag  |3 Volltext 
082 0 |a 510 
082 0 |a 500 
082 0 |a 510.28553 
520 |a Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you'll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming. Rather than use mathematical notation or an unfamiliar academic programming language like Haskell or Lisp, this book uses Ruby in a reductionist manner to present formal semantics, automata theory, and functional programming with the lambda calculus. It's ideal for programmers versed in modern languages, with little or no formal training in computer science. Understand fundamental computing concepts, such as Turing completeness in languagesDiscover how programs use dynamic semantics to communicate ideas to machinesExplore what a computer can do when reduced to its bare essentialsLearn how universal Turing machines led to today's general-purpose computersPerform complex calculations, using simple languages and cellular automataDetermine which programming language features are essential for computationExamine how halting and self-referencing make some computing problems unsolvableAnalyze programs by using abstract interpretation and type systems