2 of 59

The English word “compute” originates from the Latin word meaning to calculate.
Now forget about the mathematical implications of calculation, or a process dealing with numbers.
Only think of computing as a process starting with “input” and ending with “output”.
So, what connects the input and output?

3 of 59

In high school, such a process is usually labeled as a function.
Most of the functions we have learnt stipulate that there is a unique output for every distinct input.
But the converse need not be true.

4 of 59

VARIOUS KINDS OF FUNCTION

5 of 59

For humans, it seems that we usually get an answer (output) for a question (input) almost-instantaneously.
Think: for questions that require you to recite what you remember, is it just about the single step of retrieving the answer from the memory?
Try this: tell me the color of the clothes you wore on 30^th March 2023.
If you happen to fail to remember, how come you could not get the information stored inside your brain?
How do you know you have lost the information?
Or did you fail in your method of retrieving the information?

6 of 59

What about reasoning, or tasks that obviously require you much more than retrieving a piece of information from your brain?

Why is the famous software company named Oracle?

7 of 59

The origin of computing may be understood as the dream of the automation of thinking.
Such a process was considered as a mechanical process.
The analogy with the mechanical clock is obvious: in other words, if the movement of the cogs and wheels inside a clock can track time accurately, why not apply the same principle to other tasks?

8 of 59

BABBAGE’S ANALYTICAL ENGINE (1830S)

9 of 59

Mill: The Arithmetic Logic Unit (ALU), which performed calculations.
Store: Memory for holding numbers and intermediate results.
Reader: An input mechanism, in this case, the punched cards.
Printer: An output device to present the results of the calculations.

10 of 59

There were other varieties of thinking or reasoning machines. They all failed to materialize for a number of reasons, most importantly is the difficulty of assembling the numerous mechanical parts.
Another inherent defect is the specificity of task for each machine.
In contrast, the computer in the twentieth century is an all-purpose, or universal, machine.

11 of 59

ANALOG VS DIGITAL

One well-known reason for the breakthrough in computing in the last century is the adoption of digitalization.

In brief, analog information involves continuous quantities, whereas digital information is binary in nature.

12 of 59

NUMBER(S)

A brief revision of primary school-level mathematics: how many kinds of number have you learnt?

And, what are the different systems of representing quantities?

13 of 59

You should recall that our usual way of representing numbers is decimal. Most people find this system “natural”. But in fact it feels natural only because we have learnt it when we were small. In ancient societies, there were strange systems such as the Roman system using seven symbols:

I = 1

V = 5

X = 10

L = 50

C = 100

D = 500

M = 1,000

14 of 59

For example, TVB uses Roman numerals to show the copyright year of a program: a copyright for the year 2025 is listed as MMXXV.

15 of 59

Another ancient civilization, Babylon, used an even “weirder” base-60 (sexagesimal) system. They only needed two symbols: a wedge (𒁹) for one and a chevron (𒌋) for ten.
When we discuss deep learning in later lectures, we will note that the steepness of the learning curve may not reflect anything about the level of difficulty.

16 of 59

BINARY SYSTEM

It is now common knowledge that the computer uses a binary system: 0 and 1.
The advantages of the binary system are many. But the most crucial one is that since the middle of the 19^th century, we have known about the electromagnetic properties. Since polarization of, say, the electric charge into +ve and –ve is just physical nature, the use of the binary system can rely on the binary nature of electricity.
In the last bloc of lectures on logic, we will also learn the relevance of the binary system in terms of the important properties of true vs false.

17 of 59

Basically, the essence of contemporary computation is a device manipulating the flow of electrons in a logical manner.
One can understand the flow of an electron “in” as representing, say, the zero bit, and the flow of it “out” as the one bit (note that we are using the binary system for representing).
The pattern of the flowing “in and out” is dictated by the programmes (software, Apps, etc.) we write.
The “logic” of the “in and out” is physically implemented by the logic gates.

18 of 59

LOGIC GATES

19 of 59

We will learn the logic gates again in the last lecture on truth-table.

21 of 59

WHAT IS A COMPUTER?

I ask this question because there are subtle differences between computing and computer. As said, we can generalize the claim that a computer is any artifact that can receive input and then perform certain tasks on the input and finally ends the process with some output.
Maybe you would like to be more specific. So, you might give me a detailed list of the hardware essential to the architecture of a computer.
But the explanation needed in fact depends on the audience and purpose: it may be much better on some occasions to have our parents’ answer: “A computer is what you can buy in an Apple store and costs at least several thousand dollars”.

24 of 59

A summary of what we have in the previous diagrams (about hardware and architecture) is that we need physical memory, input device, mathematical processor, output device, and most importantly the “CPU” that can take our instructions and process them step by step until we have the output.

25 of 59

ALGORITHM

The instructions given by a programme are simply a series of rules commonly known as algorithm. Remember that the previous simple idea of input🡪 function🡪 output still applies: you may understand the programme to be a function.

Input

Function

Output

Programme

27 of 59

Binary search is an efficient algorithm for finding a target element within a sorted array or list. It operates by repeatedly dividing the search interval in half.

Once we have the idea, we can implement it in the programming language, for example Python, as an algorithm.

30 of 59

You may understand the idea behind the algorithm to be some kind of a shortcut. Mathematicians have been dealing with such shortcuts as their professional requirement for ages.
It is only in the last 80 years that computer programmers incorporate the shortcut method into their day-to-day activities.

31 of 59

HOW TO DO THIS EFFICIENTLY?

34 of 59

Perhaps common users like us are very mindful of the actual makeup of the computer we buy since we believe that some are cutting edge products (such as the latest MacBook pro or iPhone 16 pro max), whereas some are junk stuff (a 5-year-old Chromebook?).
Let me tell you that although there are obvious difference in performance between the two, in principle they are exactly the “same”.
But what do I mean by “the same”?

35 of 59

ALAN TURING

36 of 59

Have you watched the movie by Benedict Cumberbatch called Imitation Game?
The protagonist of the film is Alan Turing, the father of computer science.
Turing is a legend: he literally conceptualized the first modern-day computer and most significantly he mentally conceived what a computer is in a very short paper.

37 of 59

The paper that Turing wrote in 1950 on the topic is our reference: “Computing Machinery and Intelligence”. �https://www.csee.umbc.edu/courses/471/papers/turing.pdf

Note that at that time, Turing had already cracked the Enigma machine and written other papers on the principle of computing.

38 of 59

In this paper, his focus is not on whether a computer can be built (he and others had already built many) but about whether the kind of computer he had conceived, as well as any conceivable computer in the future, can become intelligent exactly in the human way.

Of course, “exactly in the human way” is vague.

39 of 59

TURING MACHINE

Turing demonstrated by mathematical and logical reasoning that no matter how technology and knowledge have advanced, computation by anything (machine) must be based on his model, the Turing Machine (TM).
Nowadays, we usually call Turing Machine “Universal Turing Machine” (UTM) because we believe what Turing claims about the universality of his design.

42 of 59

When Turing conceived of the computer from scratch, he in fact had a very simple diagram: the famous Turing machine diagram.

See how a LEGO Turing machine works:�https://www.youtube.com/watch?v=FTSAiF9AHN4

43 of 59

The previous two diagrams are standard ways to show what a Universal Turing Machine is.
Put simply, Turing asks us to imagine that we have several basic sets of items:

Unlimited supply of tape or paper with distinct boxes on it.
A scanner capable of recognizing and changing symbols on the tape or paper.
A set of instructions for things to be done to the tape of paper.

44 of 59

So, we have , say, a very long stretch of paper with boxes arranged linearly on it.
The symbol on the paper is either 0 or 1.
The scanner can scan the boxes and print 0 or 1 there.
The paper can also be moved left or right one box at a time.
Then scanner receives instruction in the form of a list of commands (move paper left or right or don’t move; write 0 or 1 on a box or write nothing).

45 of 59

The list of commands is what we call the programme.
The condition of the many 0 and 1 on the paper is what we call the state.
When the paper halts and nothing more will be done by the scanner, the series of 0 and 1 on the paper is our result.
Hence, by running a programme like this, we expect the stripe of paper will finally stop.

46 of 59

If we are not sure that the paper will in theory stop ultimately, there is no point in running the programme in the first place.
What is important is that a programme is “good” if it stops running, the state on it is the output we want.
If it does not stop after running a long time (it depends on your understanding), there are two possibilities: (1) it will stop later and give us the output; (2) it will keep on running for eternality.

47 of 59

You may be familiar with the second possibility: there is a bad loop in the programme or there is a bug.
Now, the practical question of whether we should wait a little bit longer for the output becomes philosophical: is there another programme to verify that this programme currently running is buggy or not?

49 of 59

Here is the explanation by ChatGPT: The Turing Entscheidungsproblem (or decision problem) is the question of whether there exists a universal algorithm that can decide if any given mathematical statement is provable within a formal logical system. Alan Turing, in his seminal 1936 paper, proved that no such algorithm can exist, thus showing that the problem is undecidable. This groundbreaking result, which also led to the concept of the first computer, established that there are fundamental limits to what can be computed and demonstrated the existence of undecidable propositions.

50 of 59

For common users, this “limitation” may sound commonsense. But in fact, it is a very important conception of computability.
In theory, if you can demonstrate that UTM is actually not universal, then the decision problem may be solved.

51 of 59

On the other hand, if you believe that a computer must be UTM in structure, then the development of computer in the last 80 years (from the slow and bulky machines to the slim and fast laptop you are using) is just a matter of increasing its speed of processing and the capacity of storage.
You may thus understand the computer to be some dumb thing capable of doing simple repetitive tasks very quickly.
The idea is that, as we will learn more in the lecture on AI, reasoning and intelligence are at the very basic level doing simple tasks repeatedly. Of course, on the higher, or conscious, level we are not aware that we are doing those things.
That’s why in the last two blocs of lectures on logical reasoning, we resort to intuitive and yet symbolic ways to encode our reasoning.

52 of 59

MOORE’S LAW

The principle that the speed and capability of computers can be expected to double every two years, as a result of increases in the number of transistors a microchip can contain.

53 of 59

THE FUTURE OF COMPUTING

Quantum computer

54 of 59

Although the supercomputers nowadays are already very very fast and have huge storage capacity, we are approaching a bottleneck of massive improvement: making the computer faster comes at a cost of heat generation.
Furthermore, the binary nature of the bits may not be the most efficient way to encode information.

56 of 59

A qubit uses the quantum mechanical phenomena of superposition to achieve a linear combination of two states. A classical binary bit can only represent a single binary value, such as 0 or 1, meaning that it can only be in one of two possible states. A qubit, however, can represent a 0, a 1, or any proportion of 0 and 1 in superposition of both states, with a certain probability of being a 0 and a certain probability of being a 1.

57 of 59

The amount of information a qubit system can represent grows exponentially. Information that 500 qubits can easily represent would not be possible with even more than 2⁵⁰⁰ classical bits.
Furthermore, in theory a quantum computer can be made from any imaginable atomic particles such as trapped ions, photons, artificial or real atoms, or quasiparticles.
The present obstacles are the problem of decoherence (some kind of interference from the environment to ruin the qubits) and the need of operating under very low temperature.

58 of 59

QUANTUM SUPREMACY

This is the contemporary key term of the quantum computing hype.
China and USA are currently investing huge amount of manpower and money on quantum computing research.
In theory, if it succeeds, the world will be dramatically changed: very like the change people experience with the first smartphone or you experience with the rise of ChatGPT 3.
One known consequence is that a quantum computer can easily break the code we use in banking and other online security transactions.

1 of 59