Difficulty: Introductory | Prerequisites: None
Before diving into specific languages, algorithms or applications, it helps to understand the small number of ideas that make computing possible at all. This section covers three foundational insights, each showing that something seemingly complex (all of computation) reduces to something surprisingly simple: two symbols, five operations, three control structures. These ideas form the theoretical bedrock of every programming language, operating system and application you will encounter in the rest of the course.
All computable information can be represented with just two symbols (0 and 1). Any algorithm can be carried out with just five basic operations (the Turing machine). Any program, however complex, can be built from just three control structures: sequence, selection and iteration.
Binary representation
The encoding of all information using two symbols: 0 and 1. Any bistable device (on/off, magnetised/demagnetised, high-voltage/low-voltage) can store one binary digit (bit).
Think of it as the alphabet of computing: just two letters, but enough to write anything.
Turing machine
A theoretical model of computation consisting of an infinite tape, a read/write head and a finite set of rules. Despite its simplicity, it can compute anything that any computer can compute.
In simple terms, a Turing machine is a thought experiment that proves five basic operations are enough to do "anything" a computer can do.
Church-Turing thesis
The hypothesis that any function which can be computed by an effective procedure can be computed by a Turing machine. It is not a proven theorem but a widely accepted foundational claim.
Think of it as the statement that there is no "more powerful" kind of computer waiting to be discovered.
Bohm-Jacopini theorem (structured program theorem)
The proof that any computable function can be expressed using only three control structures: sequence, selection (if/else) and iteration (while loops).
In simple terms, you never need more than "do this then that," "if X then Y else Z," and "while X do Y" to write any program.
Sequence
Executing instructions one after another, in order: first do this, then do that.
Selection (branching)
Choosing between two paths based on a condition: IF the condition is true, THEN do this, ELSE do that.
Iteration (looping)
Repeating a set of instructions while a condition holds: WHILE the condition is true, DO this.
Structured programming
A programming discipline that uses only sequence, selection and iteration (no arbitrary "goto" jumps), producing code that is easier to read, test and maintain.
In simple terms, writing programs using only the three control structures rather than jumping around unpredictably.
Philosopher of computing Bill Rapoport identified a cluster of insights from Leibniz, Boole, Shannon and Morse that converge on one point: a computer only needs two symbols to represent anything computable.
Gottfried Wilhelm Leibniz formalised the binary number system in the late 17th century, showing that all numbers can be expressed using just 0 and 1.
George Boole developed Boolean algebra in the 19th century, demonstrating that logical reasoning can be reduced to operations on two values: true and false (1 and 0).
Claude Shannon, in his 1937 master's thesis, showed that Boolean algebra could be implemented with electrical circuits, directly connecting abstract logic to physical hardware. This insight is the bridge between mathematical theory and the electronic computers we use.
Samuel Morse's telegraph code demonstrated that complex messages (the entire English language) can be transmitted using just two signal states: short and long (dot and dash).
Any bistable device, anything that can switch between two clearly distinct states (on/off, magnetised/demagnetised, high-voltage/low-voltage), can represent one bit of information. Chain enough bits together and you can represent anything computable.
Alan Turing's insight: there are only five actions a computer needs to perform to compute "anything."
Every algorithm can be expressed as instructions for a machine with just five primitive operations:
Move left one position on the tape
Move right one position on the tape
Read the symbol at the current position
Write 0 at the current position
Write 1 at the current position
This theoretical device is the Turing machine. It consists of an infinitely long tape divided into cells (each holding a 0 or 1), a head that reads and writes, and a state table that dictates what to do next based on the current state and the symbol under the head.
The Turing machine is not a practical device. It is a proof of concept: if a problem can be solved by any computer, it can be solved by a Turing machine. This equivalence is the basis of the Church-Turing thesis and underpins the theoretical limits of what computers can and cannot do.
Corrado Bohm and Giuseppe Jacopini proved in 1966 that any computable function can be implemented using only three control structures.
Sequence: execute instructions in order. "First do this, then do that."
Selection: branch based on a condition. "IF such-and-such is true, THEN do this, ELSE do that."
Iteration: repeat while a condition holds. "WHILE such-and-such is true, DO this."
No other control flow mechanism (notably, no "goto") is required. Any program of any complexity can be built by nesting and combining these three.
The "goto" statement was historically common in early programming languages. It allows the program to jump to an arbitrary point in the code. While goto can simplify certain patterns, it also makes programs harder to read, debug and reason about.
The Bohm-Jacopini theorem demonstrated that goto is never necessary. This theoretical result, combined with Edsger Dijkstra's influential argument against goto, gave rise to the structured programming movement: the practice of writing programs using only sequence, selection and iteration.
Structured programming produces code that is easier to follow, test and maintain. It is the default approach in all modern programming languages, even those that still technically support goto.
Students often confuse the Turing machine with a real, physical computer. It is a theoretical model, a thought experiment. Its value is in what it proves about the limits of computation, not as engineering.
"Binary means computers can only handle numbers" is a frequent misunderstanding. Binary represents everything: text, images, sound, video and instructions. What changes is the encoding scheme, not the underlying representation.
Students sometimes think the Bohm-Jacopini theorem means goto is "wrong." The theorem shows goto is unnecessary, not that using it is always a mistake. In practice, structured programming is strongly preferred because it produces clearer code, but a few low-level or performance-critical contexts still use goto.
Confusing Shannon with Turing is common. Shannon's contribution was connecting Boolean logic to electrical circuits (the hardware side). Turing's contribution was defining what computation itself is (the theoretical side). They worked on different problems.
⚠️ Be able to name the five operations of a Turing machine
⚠️ Know the three control structures from the Bohm-Jacopini theorem (sequence, selection, iteration) and be able to give a code-like example of each
⚠️ Understand why binary representation is sufficient for all computable information
⚠️ Be able to match each contributor (Leibniz, Boole, Shannon, Morse, Turing, Bohm and Jacopini) to their key insight
⚠️ Know the difference between the Turing machine (theoretical model) and the Church-Turing thesis (claim about what is computable)
True or False: A Turing machine requires at least ten basic operations to compute any algorithm.
Fill in the blank: The three control structures in the Bohm-Jacopini theorem are sequence, ________ and iteration.
True or False: Claude Shannon showed that Boolean algebra could be implemented with electrical circuits.
Fill in the blank: Any bistable device can represent one ________ of information.
True or False: The goto statement is necessary for writing any program.
Answers: 1. False (five operations). 2. Selection. 3. True. 4. Bit. 5. False (the Bohm-Jacopini theorem proves it is never necessary).
Q: What are the five basic operations of a Turing machine?
A: Move left one position, move right one position, read the symbol at the current position, write 0 at the current position, write 1 at the current position.
Q: State the Bohm-Jacopini theorem in one sentence.
A: Any computable function can be implemented using only three control structures: sequence, selection (if/else) and iteration (while loops).
Q: What was Claude Shannon's key contribution to computing?
A: Shannon demonstrated that Boolean algebra could be implemented with electrical switching circuits, connecting abstract logic to physical hardware.
Q: Explain why binary representation is sufficient for all computable information.
A: Any information about a computable problem can be represented using only 0 and 1. Any device with two distinguishable states (on/off, high/low voltage) can store one bit. By combining enough bits, arbitrarily complex information can be encoded.
Q: What is the relationship between the Bohm-Jacopini theorem and structured programming?
A: The Bohm-Jacopini theorem provided the theoretical proof that goto is unnecessary. This, combined with practical arguments about code readability and maintainability, led to the structured programming movement, which restricts programs to sequence, selection and iteration.
Binary representation connects directly to computer security and cryptography (companion study notes): encryption algorithms operate on binary data, and hash functions produce binary digests. The Bohm-Jacopini theorem connects to the programming paradigms notes: every paradigm (imperative, object-oriented, functional) implements sequence, selection and iteration in its own way. The Turing machine concept reappears in formal languages and automata theory, a topic typically covered in upper-division CS courses.
Foundational discoveries, binary representation, binary number system, bit, bistable, Leibniz, Boolean algebra, George Boole, Claude Shannon, switching circuits, Samuel Morse, Morse code, Alan Turing, Turing machine, five basic operations, Church-Turing thesis, computability, Corrado Bohm, Giuseppe Jacopini, Bohm-Jacopini theorem, structured program theorem, sequence, selection, iteration, branching, looping, if-else, while loop, goto, structured programming, Dijkstra, control structures, CS 101, Arizona State University