Computer Science | Machines and computational modelling

Welcome to Machines and Computational Modelling!

Hello Computer Scientists! This chapter might sound very theoretical, but it is actually about the fundamental rules that make every computer, phone, and video game work.

We are going to explore how we can use simple, theoretical machines to represent complex real-world systems. Understanding these basic building blocks is crucial because they define what computers can and cannot do. Don't worry if this seems tricky at first—we’ll break everything down using everyday examples!

Section 1: What is Computational Modelling?

Understanding the Need for Models

In Computer Science, a Computational Model is a simplified representation of a real-world process, system, or object. We use these models to study complex systems without having to build or experiment with the real thing.

Think of it like building a miniature car before building the full-sized version. The miniature car (the model) helps the engineers understand physics, efficiency, and design flaws cheaply and quickly.

Key Purposes of Computational Modelling:

• Prediction: Predicting what will happen next (e.g., weather forecasting).
• Understanding: Helping us see how complex systems interact (e.g., modelling traffic flow).
• Testing: Trying out different scenarios safely (e.g., testing flight controls in a simulator).
• Design: Creating a plan before writing the actual program code.

Key Takeaway: Models simplify the complex world into manageable rules so computers can process them.

Section 2: Finite State Machines (FSMs)

Introducing the Simplest Machine Model

One of the most common and easiest computational models to understand is the Finite State Machine (FSM). An FSM is a machine that can only be in one of a small, fixed number of situations (called states) at any given time.

The machine moves between these states based on specific inputs it receives. This movement is called a transition.

The Three Core Components of an FSM:

1. States: The current situation or condition of the machine. The number of states is always finite (limited).
2. Inputs: Signals or data that cause the machine to react.
3. Transitions: The rules that dictate which state the machine moves to when a specific input is received.

Real-World Example: The Traffic Light

A traffic light is a perfect example of a Finite State Machine.

Imagine a single traffic light controlling one lane of traffic.

The States:

• State 1: RED (Stop)
• State 2: RED & AMBER (Prepare to go)
• State 3: GREEN (Go)
• State 4: AMBER (Prepare to stop)

The Transitions (What makes it move to the next state):

• If the light is RED, the input (Time elapsed) causes the transition to RED & AMBER.
• If the light is GREEN, the input (Time elapsed) causes the transition to AMBER.

Notice that the light cannot jump directly from RED to GREEN—it must follow the set transition path!

Section 3: The Universal Model – The Turing Machine

Alan Turing and the Limits of Computation

While FSMs are useful for simple systems, in the 1930s, mathematician Alan Turing developed a theoretical model that could execute any computational task a modern computer can—no matter how complex. This model is known as the Turing Machine (TM).

The Turing Machine is not a physical computer you can buy; it is a thought experiment used to define precisely what computation is and what problems are solvable by a machine.

What is a Turing Machine made of?

The Turing Machine is surprisingly simple, yet incredibly powerful. It consists of three main parts:

1. The Infinite Tape: This acts as the machine's memory. It is divided into cells, and each cell holds a single symbol (usually 1 or 0, or a blank space). Crucially, the tape is infinite in length, meaning the machine never runs out of memory.
2. The Read/Write Head: This device sits over one cell of the tape at a time. It can:
   • Read the symbol in the current cell.
   • Write a new symbol into the current cell.
   • Move one cell to the left or one cell to the right.
3. The State Register: This holds the current state of the machine (similar to the states in an FSM). The state determines what the head does next.

Step-by-Step Process: The machine reads the symbol and looks at its current state. Based on these two things (symbol + state), it follows a rule to: 1) Write a new symbol, 2) Move the head (Left/Right), and 3) Change to a new state. It repeats this until it reaches a "HALT" state.

Why is the Turing Machine Important?

Any computer system today, from the fastest supercomputer to the simplest smartphone, is functionally equivalent to a Turing Machine.

• A machine that can simulate any other Turing Machine is called a Universal Turing Machine (UTM).
• This concept proves that a single, standard type of machine can solve every solvable computational problem. This is why your laptop can run games, spreadsheets, and web browsers—it's a UTM!

Section 4: Solvability and the Limits of Computation

What Problems Can Machines Solve?

The Turing Machine model helps us determine if a problem is computable (solvable by a machine) or non-computable (impossible to solve algorithmically).

For a problem to be computable, we must be able to create a finite set of clear, unambiguous steps (an algorithm) that the Turing Machine can follow to reach a solution and eventually halt (stop).

Common Pitfall: The Halting Problem

One of the most famous examples of a non-computable problem is the Halting Problem.

The Halting Problem asks: Is it possible to write a general algorithm that can look at any other program and its input, and correctly determine whether that program will eventually finish (halt) or run forever in an infinite loop?

Alan Turing proved that such an algorithm cannot exist. It is impossible for a machine to reliably predict if *every* other arbitrary program will halt. This sets a fundamental limit on what computers can do!

Memory Aid: Computers are great, but even they have limits! The Halting Problem proves that computers cannot perfectly predict the future behaviour of all other programs.

Summary of Key Takeaways

We use Computational Models (like FSMs and Turing Machines) to define, simplify, and test real-world systems.

• The Finite State Machine (FSM) uses a limited number of States and predefined Transitions to model simple processes.
• The Turing Machine (TM) is the theoretical definition of computation, using an Infinite Tape and a Read/Write Head. It proves that a single simple machine can perform any solvable task.
• The Halting Problem demonstrates that there are limits to computation; some logical problems are fundamentally non-computable.

Keep practising how to identify states and transitions in simple scenarios (like a light switch or a padlock combination). You’ve mastered the core concepts that define modern computing! Great work!