Understanding Computation Read Online Free

around with.
    Programs aren’t much use without machines to run them on, so in Chapter 3 , we’ll design very simple machines capable of performing
     basic, hardcoded tasks. From that humble foundation, we’ll work our way up to more
     sophisticated machines in Chapter 4 , and in Chapter 5 , we’ll see how to design a general-purpose computing device
     that can be controlled with software.
    By the time we reach Part II , we’ll have seen the
     full spectrum of computational power: some machines with very limited capabilities, others
     that are more useful but still frustratingly constrained, and finally, the most powerful
     machines that we know how to build.

Chapter 2. The Meaning of Programs
    Don’t think, feel ! It is like a finger pointing
    away to the moon. Don’t concentrate on the finger or you will miss all
    that heavenly glory.
    — Bruce Lee
    Programming languages,and the programs we write in them, are fundamental to our work as software
    engineers. We use them to clarify complex ideas to ourselves, communicate those ideas to each
    other, and, most important, implement those ideas inside our computers. Just as human society
    couldn’t operate without natural languages, so the global community of programmers relies on
    programming languages to transmit and implement our ideas, with each successful program forming
    part of a foundation upon which the next layer of ideas can be built.
    Programmers tend to be practical, pragmatic creatures. We often learn
a new programming language by reading documentation, following tutorials,
studying existing programs, and tinkering with simple programs of our own,
without giving much thought to what those programs mean . Sometimes the learning process feels a lot like
trial and error: we try to understand a piece of a language by looking at
examples and documentation, then we try to write something in it, then
everything blows up and we have to go back and try again until we manage to
assemble something that mostly works. As computers and the systems they
support become increasingly complex, it’s tempting to think of programs as
opaque incantations that represent only themselves and work only by
chance.
    But computer programming isn’t really about programs , it’s about ideas .A program is a frozen representation of an idea, a snapshot of a structure that once
    existed in a programmer’s imagination. Programs are only worth writing because they have meaning . So what connects code to its meaning, and how can we be more
    concrete about the meaning of a program than saying “it just does whatever it does”? In this
    chapter, we’re going to look at a few techniques for nailing down the meanings of computer
    programs and see how to bring those dead snapshots to life.
    The Meaning of “Meaning”
    In linguistics,
semantics
is the study of the connection between words and their
    meanings: the word “dog” is an arrangement of shapes on a page, or a
    sequence of vibrations in the air caused by someone’s vocal cords, which
    are very different things from an actual dog or the idea of dogs in
    general. Semantics is concerned with how these concrete signifiers relate
    to their abstract meanings, as well as the fundamental nature of the
    abstract meanings themselves.
    In computer science, the field of
formal
    semantics
isconcerned with finding ways of nailing down the elusive
    meanings of programs and using them to discover or prove interesting
    things about programming languages. Formal semantics has a wide spectrum
    of uses, from concrete applications like specifying new languages and
    devising compiler optimizations, to more abstract ones like constructing
    mathematical proofs of the correctness of programs.
    To completely specify aprogramming language, we need to provide two things:a
syntax
, which describes what programs look like, and a semantics, [ 2 ] which describes what programs mean.
    Plenty of languages don’t have an official written