Chapter 1

Computational Models

The dawn of modern computing, in the years immediately following the Second World War, was characterized not only by practical ingenuity in the construction of the first calculating machines, but also by the establishment of solid theoretical foundations that would guide the development of the discipline for decades to come. In this chapter, we will explore some of the most influential computational models that have laid the foundation for understanding and building computing systems.

1.1 The Turing Machine:
Defining the Limits of Computation

In 1936, well before the construction of the first electronic computers, the British mathematician Alan Turing published a seminal article entitled "On Computable Numbers, with an Application to the Entscheidungsproblem". In this work, Turing proposed an abstract model of a computer, now universally known as Turing Machine . This was not a physical machine in the traditional sense, but rather a theoretical construct, a thought experiment designed to answer a fundamental and deeply philosophical question: What problems can be solved by an algorithmic process, that is, by a finite sequence of unambiguous instructions?

A Turing Machine is conceptually composed of:

An infinite ribbon: Imagine an unlimited ribbon in both directions, divided into contiguous cells.

Each cell can contain a single symbol from a finite alphabet, which includes at least one special symbol to indicate an empty cell (often denoted 'B' or '□').

A head: A mechanism capable of positioning itself on a specific cell of the tape. This head has the ability to read the symbol present in the current cell, write a new symbol in the same cell and move one position to the right or left along the tape.
A finite set of states: The machine is in a specific state at all times. This set of states is finite and includes an initial state (from which the computation begins) and one or more final (or acceptance) states, which indicate the end of a successful computation.
A transition function: The heart of the Turing Machine is its transition function. This function, which can be represented as a table or a set of rules, determines the behavior of the machine in each step. Based on the current state of the machine and the symbol read by the head, the transition function uniquely specifies three actions: The symbol to write to the current cell (which could be the same symbol read). The direction in which the head should move (left, right, or, in some definitions, stay still). The new state the machine must go into.
The symbol to write on the current cell (which could be the same symbol read).
The direction in which the head should move (left, right, or, in some definitions, stay still).
The new state the machine must go into.

The conceptual importance of the Turing Machine is extraordinary. It provided a precise and rigorous formalization of the intuitive concept of algorithm. The key idea is that any computational process that can be described by a finite set of unambiguous rules can be simulated by a Turing Machine.

This notion is formalized in the Church-Turing Thesis , a fundamental principle (not mathematically provable but widely accepted) which states that any function computable by a human following a set of mechanical rules can be computed by a Turing Machine.

The Turing Machine not only provided a working definition of computability, but also made it possible to explore the intrinsic limits of computation. For example, Turing himself used his model to demonstrate the existence of undecidable problems , i.e. problems for which there is no algorithm (and therefore no Turing Machine) capable of providing a definitive answer (yes or no) for all possible instances. An emblematic example is the Halting Problem : given a program (or a Turing Machine) and its input, is it possible to determine whether the program will end its execution or continue to run infinitely? Turing proved that there is no general algorithm to solve this problem.

1.2 The Von Neumann Model:
The Architecture of Modern Computers

While the Turing Machine represented a theoretical model of computation, the architecture proposed by John von Neumann, in collaboration with other pioneers such as John Presper Eckert and John William Mauchly, provided the conceptual blueprint on which the vast majority of modern computers are based. This architecture, first described in an influential 1945 report titled “First Draft of a Report on the EDVAC,” introduces some fundamental principles that still define the structure of our computers today:

Central processing unit (CPU): The "brain" of the computer, responsible for executing instructions. The CPU is further divided into: Control Unit (CU): Retrieves instructions from memory, decodes them and generates the control signals necessary to coordinate the other components of the system. Arithmetic-logical unit (ALU): Performs arithmetic (addition, subtraction, multiplication, division) and logical (AND, OR, NOT) operations on data.
Control Unit (CU): Retrieves instructions from memory, decodes them and generates the control signals necessary to coordinate the other components of the system.
Arithmetic-logical unit (ALU): Performs arithmetic (addition, subtraction, multiplication, division) and logical (AND, OR, NOT) operations on data.
Memory: Used to store both the data to be processed and the program instructions. This memory is conceptually organized as a sequence of locations, each identified by a unique address. Memory allows direct access to any location in a relatively constant time (random access memory or RAM).
Input/output (I/O) devices: Allow the computer to interact with the outside world. Input devices allow you to enter data and commands into the computer (e.g., keyboard, mouse), while output devices allow you to display or transmit the results of processing (e.g., monitor, printer).
Bus: A system of conductors (wires or traces on a printed circuit board) that serves as a communication route between the different components of the system. There are usually three main types of buses: Data bus: Transports data between the CPU, memory and I/O devices. Address Bus: Specifies the memory or I/O device address being accessed. Control bus: Carries control signals that coordinate operations between different components.
Data bus: Transports data between the CPU, memory, and I/O devices.
Address Bus: Specifies the memory or I/O device address being accessed.
Control bus: Carries control signals that coordinate operations between the different components.

A fundamental conceptual element of the von Neumann architecture is the concept of stored program . This means that both the program instructions and the data they operate on are stored in the same memory. This seemingly simple idea represented a crucial departure from early computers, where instructions were often hardwired directly into the hardware or stored on separate media.

The stored program offers enormous flexibility, as it allows you to change the behavior of the computer simply by loading a new program into memory. It also allows you to treat instructions as data, paving the way for advanced techniques such as modifying code at runtime.

While von Neumann's architecture was incredibly influential and underlies most of the computers we use today, it also has some inherent limitations. The best known is the von Neumann bottleneck . Because both data and instructions must pass through the same memory bus, the processor's execution speed can be limited by how quickly data and instructions can be fetched from memory. To overcome this limitation, several techniques have been developed, such as the use of cache memories and alternative architectures. A significant alternative architecture is the Harvard architecture , used in some specialized systems such as digital signal processors (DSPs), which physically separates instruction memory from data memory, allowing both to be accessed simultaneously.

1.3 Shannon's Information Theory:
Measuring Uncertainty

Simultaneously with the development of the first computers and the formalization of computational models, Claude Shannon's pioneering work on information theory , published in his seminal 1948 article "A Mathematical Theory of Communication", provided a rigorous theoretical framework for quantifying and understanding the concept of information. This work has had a profound impact not only on computer science, but also on telecommunications engineering and many other fields.

Shannon defined information in terms of uncertainty reduction. In other words, the information contained in a message is proportional to the surprise it generates. The more unexpected an event or message is, the more information it conveys. To quantify this idea, Shannon introduced the fundamental unit of information: the bit (binary digit). One bit represents the amount of information needed to resolve an uncertainty between two equally probable alternatives (for example, the outcome of a coin toss).

Mathematically, the amount of information (H) of an event with probability p of occurring is defined as:

H = -log₂(p)

Where the logarithm is base 2, reflecting the binary nature of the bit.

Shannon information theory provided the fundamental mathematical tools for:

Measuring the amount of information contained in a data source or message. This allowed us to define the maximum capacity of a communication channel (the so-called Shannon-Hartley theorem).
Understanding the theoretical limits of data compression . Shannon theory sets a lower limit to the size to which a data set can be compressed without loss of information (entropy).
Design reliable communication systems even in the presence of noise or interference. The theory of error correcting codes, developed from Shannon's work, allows redundancy to be added to transmitted data so that errors introduced by the communication channel can be detected and corrected.

The concept of bit, derived from Shannon's theory, has become the fundamental unit for representing and manipulating information within computer systems. Every piece of data, every instruction, every image or sound within a computer is ultimately encoded as a sequence of bits.

The computational models of Turing and von Neumann, together with Shannon's information theory, represent the theoretical pillars on which the field of computer science was built and continues to evolve. The Turing Machine provided a formal definition of computability and allowed us to explore the limits of algorithmic computation. The von Neumann architecture offered a practical and flexible design for making electronic computers, which dominated the industry for decades.

Finally, Shannon's information theory provided a mathematical framework for understanding and managing information, a central element of any computer system. Understanding these fundamental concepts is not only essential for computer science students, but also offers a deep perspective on the intellectual roots of this discipline that continues to transform our world.