Computation, Machines and Languages

Where this course takes you

Sixteen weeks from now, you should be able to do the following.

Take a problem described in plain language — count how often each surname appears in this list, say — break it into steps, write it in Python, get it running, and know which line to look at when it goes wrong.

Read code somebody else wrote, follow what it does, judge whether it is any good, and spot the input that would break it.

And work alongside an AI assistant. Not by handing your thinking to it, but by knowing what to ask it for, what to keep for yourself, and how to check whatever it gives back.

No prior experience is assumed. If you did some programming in secondary school, good. If you have never written a line and are not entirely sure what a “program” is, that is fine too — this course was built for you.

Computation

People did it for thousands of years

Before there were computers, computing was something people did. The abacus, the slide rule, the vast printed tables of logarithms sitting in every observatory — all of it existed to help humans calculate faster and get it wrong less often.

Astronomers and navigators needed enormous tables of trigonometric and logarithmic values, and those tables were produced by hand, by people employed for the purpose. The word “computer” originally meant a person who computes.

The trouble is that people get tired, lose concentration, and make mistakes. And once a page of a table is wrong, every navigation chart built on it is wrong too.

In the nineteenth century, Charles Babbage set out to build a machine for the job. His Analytical Engine already had recognizable versions of a processor, a memory, and input and output, and it was to be programmed with punched cards. It was never built — the machining tolerances of the day were not good enough — but the designs survive, which is why Babbage is usually called the father of the computer.

Ada Lovelace (1815–1852), who worked with him, wrote a sequence of instructions for the Engine to compute Bernoulli numbers. It is generally regarded as the first computer program — written for a machine that never existed, a century before one did.

She also saw something Babbage did not. The Engine need not be limited to numbers. Encode something else — musical notes, for instance — as numbers, and the machine can operate on that too. Every piece of digital technology you use rests on that observation.

Three leaps

Getting machines to compute took three quite different physical tricks:

Each leap did the same thing: make the switch smaller, faster, and cheaper to run.

The transistor, invented at Bell Labs in 1947, was the decisive step. The MOS 6502 of 1970 carried 3,500 transistors. A phone chip today carries tens of billions. Feature sizes went from 10 micrometers to 3 nanometers — and 3 nanometers is roughly a dozen silicon atoms side by side.

What Moore’s law says

In 1965 Gordon Moore, one of Intel’s founders, noticed a pattern: the number of transistors on an integrated circuit roughly doubles every eighteen months.

There are three equivalent ways to read that, and all three matter:

• Performance — for the same money, in eighteen months you can buy a machine twice as fast
• Price — for the same performance, in eighteen months it costs half as much
• Size — for the same capability, in eighteen months it takes half the space

It is not a law of physics. It is an empirical observation, and it has clearly slowed in recent years. But it shaped half a century of the industry, and the phone in your pocket outperforms a 1990s supercomputer.

What that means for you: a great many problems that were simply out of reach twenty years ago can now be attacked by brute force. Computation has become the route by which scientific theory reaches reality. For problems too tangled to reason through on paper, building a model, designing an algorithm and letting a machine grind through it is often the only path available.

A moment worth marking

In 1997 IBM’s Deep Blue beat world chess champion Garry Kasparov. In 2016 AlphaGo beat Lee Sedol at Go.

Nineteen years separate them, because Go’s search space dwarfs chess’s and Deep Blue’s approach — enumerate everything — does not scale to it. AlphaGo took a different route. It stopped enumerating and started learning.

You are arriving at the next stage of that line. The current models do not just play games; they write code. What that means for this course is the subject of the last section.

How a computer is put together

The von Neumann architecture

In 1945 John von Neumann described a machine structure in a technical report. Nearly every computer you will ever touch — phone, laptop, server, router — is a variation on it.

Five parts:

The most important detail, and the easiest one to skim past: programs and data live in the same place, in the same form.

This is the stored-program idea. One consequence is that the machine does not need rewiring to switch tasks — you just load a different program into memory. The other consequence is subtler: a program can be treated as data. Compilers, interpreters, and a good number of the techniques you will meet later in this course all grow from that root.

Everything is ones and zeros

What is actually in memory? Two states, high voltage and low voltage, which we write as 1 and 0.

A single 0 or 1 is a bit. Eight bits make a byte.

Which raises the question: what does a given string of ones and zeros mean?

The answer is that it depends entirely on how you agree to read it. Take 01000001:

• read as an integer, it is 65
• read as an ASCII character, it is the letter A
• read as a machine instruction, it might be some CPU opcode
• read as a pixel, it might be a shade of gray

A sequence of bits carries no meaning by itself. Meaning comes from convention. That idea is one of the keys to the whole subject, and L2 takes it apart properly.

For now, get a feel for how the bases line up:

n = 2026

print("decimal:    ", n)
print("binary:     ", bin(n))
print("octal:      ", oct(n))
print("hexadecimal:", hex(n))

# and back again
print(int("11111101010", 2))

Software and the operating system

Hardware is a pile of components with electricity running through it. Making it do something useful takes software — instructions, data, programs.

The most important piece of software on any machine is the operating system. It manages the hardware and offers every other program a uniform set of services:

• when you write open("data.txt"), you do not have to know which track the disk head is on
• when your browser and your music player are both open, the OS decides who gets the CPU right now
• when you press a key, the OS routes that event to the window in front

Windows, macOS, Linux, iOS, Android — all operating systems. The labs will get you onto a Linux command line (Lab 8), because essentially every server and computing cluster you will ever use runs Linux.

Three ideas underneath all of this

Computers did not arrive by engineering alone. In the 1930s and 40s, three people answered three fundamental questions.

Turing: what does “computable” mean

In 1936 Alan Turing (1912–1954) described a deliberately minimal imaginary machine: an infinite tape, a head that reads and writes one cell at a time, and a table of state transitions. That is all it can do — read a cell, write a cell, move one step left or right.

The machine is absurdly simple, and Turing proved that anything that can be computed mechanically at all can be computed by it.

That gave a precise meaning to a previously vague word. It also drew a boundary: some problems cannot be solved by any computer. Not slowly — not at all. The famous one is the halting problem. No program exists that can look at an arbitrary program and decide whether it will run forever.

Turing’s wartime work breaking the German Enigma cipher had a material effect on the outcome. Computer science’s highest award carries his name.

Shannon: information can be measured

Claude Shannon (1916–2001) did two things.

In 1937 his master’s thesis showed that Boolean algebra — true and false, and, or, not — could be implemented with relay circuits. That paper made digital logic possible, and every digital circuit since descends from it.

In 1948 he published A Mathematical Theory of Communication, which measured information in bits and established a hard limit on how much a channel can carry. Mobile communication, file compression, and error-correcting codes all rest on it.

Gödel: formal systems have limits

In 1931 Kurt Gödel (1906–1978) proved his incompleteness theorems: any sufficiently powerful and internally consistent formal system contains statements that can neither be proved nor disproved within it.

That ended the era’s ambition of putting all of mathematics on one complete axiomatic footing. Turing’s halting problem, and the whole family of undecidability results in computer science, are the same fact wearing different clothes.

Together the three are one story from three angles: what can be computed (Turing), what we are computing with (Shannon), and what cannot be settled at all (Gödel).

Language, between people and machines

The same Hello World

A CPU understands ones and zeros. A programming language is the translation layer between it and you.

Here is one task — print Hello world — written at three levels.

Machine code, which the CPU executes directly:

01001000 01100101 01101100 01101100 01101111

Assembly, which gives those instructions readable names:

section .text
    global _start
_start:
    mov edx, len
    mov ecx, msg
    mov ebx, 1
    mov eax, 4
    int 0x80

Python:

print("Hello world")

All three do the same thing. The difference is that the first requires you to know the CPU’s instruction encoding, and the third requires you to say what you want.

Languages have moved steadily in one direction: away from the machine and toward the person. The cost is speed — the higher the language, the more translation sits underneath, and the slower it usually runs. That is a trade: machine time for human time. And by Moore’s law, machine time keeps getting cheaper while human time does not.

Why Python here

There are hundreds of languages. Choosing one to teach beginners is not arbitrary.

Learning a language means learning two things: its syntax (what is legal to write) and its semantics (what it means). For a beginner, the syntax should demand as little attention as possible, so that attention can go to the semantics and to the problem itself.

Compare, for the same one-line task:

// C
#include <stdio.h>
int main() {
    printf("Hello world\n");
    return 0;
}

// Java
public class Hello {
    public static void main(String[] args) {
        System.out.println("Hello world");
    }
}

# Python
print("Hello world")

In the C and Java versions, #include, int main, public static void are all things a newcomer has to be told about — and none of them has anything to do with printing a line of text.

Python’s trade-offs:

• Gentle for beginners — compact syntax, few incidental details, a shallow learning curve
• Genuinely useful — scientific computing, data analysis, machine learning, web work, automation. You will very likely meet it again in later courses and in research
• Open — open source, controlled by no single company, with an enormous community

The price is speed. Pure Python runs one to two orders of magnitude slower than C. For most work that does not matter, and where it does, libraries like NumPy — written in C underneath — take over.

Where Python came from

Guido van Rossum began writing Python over the Christmas break of 1989. The name comes from the comedy troupe Monty Python, not the snake.

One piece of history is worth knowing: Python 3.0, released in 2008, was not backward compatible. Code written for Python 2 does not necessarily run on Python 3. The split fractured the ecosystem for a decade, and only really ended when Python 2 reached end of life in 2020.

This course uses Python 3.13. If you find old code online that says print "hello" without parentheses, that is Python 2 and it will not run.

What happens when you run a program

The .py file you write is a text file, and the CPU cannot read it. Something has to translate. There are two approaches.

A compiler translates the whole source program into machine code ahead of time, producing an executable. After that, running it means running that file. C, C++ and Rust work this way.

• Fast at runtime, because the translation is paid for once
• But you recompile after every change, and the output only runs on the platform it was built for

An interpreter does no translation up front. It reads and executes the program a piece at a time, as it runs. Python and JavaScript work this way.

• Change something and run it immediately; portable across platforms; you can try single lines interactively
• Slower, because the translation cost is paid on every run

Python is interpreted. The python command you install is the interpreter — specifically an interpreter written in C, called CPython. (Other implementations exist, such as PyPy and Jython. This course does not use them.)

The real picture is slightly more layered. CPython first compiles your source into an intermediate form called bytecode, and a virtual machine executes that. This is why a __pycache__ folder appears in your project directory — the .pyc files inside are cached bytecode. We come back to this in L10.

import sys

print("Python version:", sys.version.split()[0])
print("Platform:      ", sys.platform)

What an IDE is

An IDE — integrated development environment — bundles the tools you need while writing code: an editor, a run button, a debugger, error highlighting, completion.

This course recommends Visual Studio Code. It is free, cross-platform, and well supported. PyCharm is also excellent, and its professional edition is free for students with a university email address.

IDLE and the bare command line, which ship with Python, are fine for trying a couple of lines. Do not write your assignments in them.

Full setup instructions are in Lab 1, and the first lab session walks through them.

Why Python is free

You downloaded Python without paying and without registering. That is not the natural order of things.

In the 1960s, computer companies made their money on hardware and gave software away with it. As hardware got cheaper and margins thinner, vendors began charging for software separately — and stopped shipping source code.

The free software and open source movements were the reaction: source code should be public, and anyone should be free to use and modify it. The mechanism is the license, a legal document stating what others may do with your code. MIT, Apache, BSD and GPL are the common ones, and they differ mainly on whether modifications must also be released openly.

In 1991 a Finnish student named Linus Torvalds posted to a mailing list that he was building a free operating system — “just a hobby, won’t be big and professional like gnu.” That was Linux. Today it runs the overwhelming majority of the world’s servers and sits inside every Android phone.

Python itself, NumPy, Matplotlib, and essentially every scientific computing tool you will use are open source. You are standing on decades of unpaid work by thousands of people. Worth knowing.

Your first program

print("Hello world")

Press Run.

print is a function. It displays whatever is inside the parentheses. The text in quotes is a string, and it comes out exactly as written.

A few more:

print("Shanghai Jiao Tong University")
print("上海交通大学")
print(2026)
print(1 + 2 + 3 + 4 + 5)

Look at the last two. In print(2026) there are no quotes, so 2026 is a number. In print(1 + 2 + 3 + 4 + 5), Python works out 15 first and prints that. What is inside quotes comes out literally; what is outside gets evaluated first.

The Zen of Python

Type import this into an interpreter and you get a short text:

import this

These are the Python community’s design values, written by Tim Peters. A few you can already use:

• Beautiful is better than ugly.
• Explicit is better than implicit.
• Simple is better than complex.
• Readability counts.
• There should be one — and preferably only one — obvious way to do it.

Right now these read as platitudes. Come back to them after L13 and they will read very differently.

How the course runs

Structure

Sixteen lectures in six parts, each closing on a specific capability:

Thirty-two hours of lectures, thirty-two hours of labs. The labs are where you actually learn. Lectures can make you follow an idea; only writing the code, breaking it, and fixing it turns that into ability.

Assessment

The AI policy

This is the most important rule in the course. Please read it properly.

Weeks 1–7: no AI-generated or AI-completed code. Turn off AI completion in your editor. You may ask an AI to explain a concept, look something up, or interpret an error message. You may not have it write code for you.

From week 8: allowed, with a declaration attached to every submission stating which tool you used, which parts it produced, and how you verified them.

Weeks 15–16, the team project: no restrictions.

Why the first seven weeks are closed — and this needs saying plainly, or the rule reads as bureaucracy:

Those weeks are where you build a feel for code and the ability to debug. Looking at a fragment and predicting its output. Reading an error and guessing which line caused it. There is no shortcut to either. You get them by writing code, getting it wrong, and finding the problem yourself.

Hand that stage to an AI and you end up with a pile of working code and no ability to judge whether code is correct. From week 8 onward that judgment is the most valuable thing you bring. Models routinely produce code that looks entirely sensible and collapses on an edge case. Without those seven weeks, you will not see it coming.

Put another way: the restriction exists so that you can genuinely use AI later, rather than be led around by it.

The full rules are on the AI policy page.

When you get stuck

In this order:

1. Read the error. It usually names the line and the problem outright. The most common beginner failure is panicking at red text without reading a word of it.
2. Check the documentation. docs.python.org is the reference.
3. Search. Paste the distinctive part of the error message into a search engine. Someone has almost certainly hit it before.
4. Ask a classmate or a TA. Questions in the course group get answered.
5. Ask an AI — within whatever the policy currently allows.

Exercises

1. Install Python and VS Code on your own machine and get print("Hello world") running. Full instructions in Lab 1.
2. Use print() to output your name, your student number, and one sentence of your choosing.
3. Use bin(), oct() and hex() to see what your student number looks like in base 2, 8 and 16.
4. Run import this. Pick the line you agree with most right now and think about what it might mean in practice. Come back at the end of term and see whether your pick has changed.
5. Break a line of code on purpose — use full-width parentheses, or misspell print as pirnt — and look at the error. Start reading error messages on day one.