Source: Section Notes 0, University of Michigan
Difficulty: Introductory | Prerequisites: None beyond basic familiarity with binary numbers.
EECS 376 treats computation as an abstract, mathematical process, and for that to work, we need a universal way to represent information. This short section introduces the course's answer: everything is a bitstring. Numbers, text, images, programs, even the inputs to programs, can all be encoded as sequences of 0s and 1s. This abstraction is what lets us reason about computation in general, without getting tied to any particular data type or programming language.
In this course, all information is represented as bitstrings (sequences of 0s and 1s). Numbers use binary notation, text uses encodings like ASCII, and even programs and their inputs are just bitstrings. This universal representation is what allows us to study computation as a single, unified subject.
Bitstring
A finite sequence of bits (0s and 1s). In EECS 376, this is the fundamental unit of information. Think of it as the universal container: anything you want a computer to process can be packed into one.
Binary notation
A positional number system using base 2. Each digit (bit) represents a power of 2. For example, 10011 in binary is 1×2⁴ + 0×2³ + 0×2² + 1×2¹ + 1×2⁰ = 19 in decimal.
ASCII (American Standard Code for Information Interchange)
A character encoding that maps each character (letters, digits, punctuation) to a number between 0 and 127. Each character therefore becomes a 7-bit bitstring. In simple terms, it is one standard way to turn text into numbers (and therefore into bitstrings).
Encoding
A scheme for representing one type of information (numbers, text, images, programs) as bitstrings. The key insight of this section is that any information can be encoded this way.
Binary notation represents integers using powers of 2. Larger numbers need more bits. The number 100 takes 3 decimal digits but 7 binary digits (1100100). The number 19 takes 2 decimal digits but 5 binary bits (10011).
In general, representing a number N in binary requires roughly ⌊log₂ N⌋ + 1 bits.
ASCII maps each character to a number (and therefore a bitstring). A word becomes a sequence of character codes, each 7 bits. Longer documents are just longer bitstrings. Other encodings exist (Unicode, UTF-8), but the principle is the same.
This is the conceptual leap: programs themselves are information, and can be represented as bitstrings. A compiler, for instance, takes as input the source code of another program, which is itself a bitstring.
The inputs to programs are also bitstrings. The bitstring might encode a number, a graph, a text file, or even another program's source code. For the purposes of EECS 376, regardless of what the bitstring represents in practice, it is formally just a bitstring.
Files, websites, images, and computer programs can all be represented as bitstrings. This uniform abstraction is what makes it possible to study computation without being tied to a specific data type. When the course later defines formal models of computation (like Turing machines), both the program and its input will be bitstrings.
Students sometimes think "everything is a bitstring" is just a slogan. It is a foundational modelling choice that the rest of the course depends on. When you later encounter Turing machines, the tape is literally a bitstring.
A bitstring is not the same as a binary number. The string 00101 is a valid 5-bit bitstring, but as a binary number the leading zeros are dropped. Context determines the interpretation.
Students occasionally assume that different types of data need fundamentally different computational models. They do not: the same Turing machine model handles numbers, text, and programs, because all are bitstrings.
⚠️ The idea that "everything is a bitstring" is assumed throughout the rest of the course. You will not be asked to prove it, but you need to be comfortable with it as a modelling assumption.
⚠️ Knowing how many bits are needed to represent a number (roughly log₂ N) comes up when analysing input sizes for algorithms.
⚠️ The fact that a program can take another program as input is the foundation for later topics on undecidability and the halting problem.
How many bits does the number 255 require in binary? (8 bits: 11111111)
True or false: A JPEG image can be represented as a bitstring. (True)
Fill in the blank: The number of bits needed to represent a positive integer N is approximately ____. (⌊log₂ N⌋ + 1)
True or false: In EECS 376, the input to a program is always a bitstring. (True)
Q: Convert the decimal number 42 to binary.
A: 42 = 32 + 8 + 2 = 2⁵ + 2³ + 2¹ = 101010 in binary.
Q: How many distinct values can a 4-bit bitstring represent?
A: 2⁴ = 16 distinct values (from 0000 to 1111).
Q: Why does EECS 376 model all information as bitstrings rather than using different representations for different data types?
A: A uniform representation lets us define a single formal model of computation (such as a Turing machine) that handles all types of input. Without this abstraction, we would need separate theories for numbers, text, images, and so on.
Q: If a program's input is the source code of another program, what type of object is that input, formally?
A: A bitstring. Regardless of what the input represents in practice, in the formal model it is a bitstring.
This section sets up everything that follows in EECS 376. When you study Turing machines, the tape is a bitstring. When you study decidability and the halting problem, both the program being analysed and the input it receives are bitstrings. The number of bits needed to represent an input (roughly log₂ of its value) also connects directly to Big-O analysis, where input size determines running time.
Bitstring, binary representation, binary notation, base 2, ASCII encoding, Unicode, UTF-8, character encoding, information representation, bits, bytes, program as data, input encoding, Turing machine tape, computational model, EECS 376, foundations of computer science