A 'universal calculator', also called a universal machine, is an exceptional kind of Turing machine, a math computation device.
These machines are named in honour of Alan Turing, featured on the new £50 banknote of 2021 in England【A1】.
Known as the father of computing, Alan Turing was born in 1912.
As a young boy, he was shy, and became attached to his mother, Sara Turing.
When little Alan first learned arithmetic, he had trouble doing long multiplication.
Sara patiently explained the method: getting row by row, shifting and adding, doing step by step.
This idea of solving a math problem by breaking down into simple parts, then work out the steps, planted a seed in Alan's mind.
He became fascinated with math, showing his talents in tackling math problems. He used his own method, sometimes even invented his own notation.
Before he was 16, he read Einstein's work. He grasped it totally, and wrote a little pamphlet on relativity for his mother【A2】.
In this episode, we shall take a look at:
the simplicity of calculating machines,
the marvelous idea of universal calculation,
how the idea was born, and how to apply to pure math,
the beauty of idea threads when dots are connected by links.
Remember, it is ok not to understand, just to admire is enough.
生於1912年的 Alan Turing，有「計算機之父」之稱。年幼時為害羞男孩，總是常常依附母親 Sara Turing (薩拉·圖靈) 。
小小 Alan 起初練習算術時，不懂如何做長乘法。Sara 耐心地講解方法：逐行計算，移位相加，循序漸進。
他意識到：解決數學問題，首先分解成為簡單的部分，然後製定步驟。這種想法，在 Alan 內心開始萌芽。他漸漸對數學著迷，在對付數學難題時，展現自己的才華。他自創方法，甚至自創符號。
仍未滿16歲，已閱讀愛因斯坦的著作。他完全掌握內容，並寫了一本「相對論」小冊子，送給母親【A2】。
本期節目，我們一齊來看一看：
計算機器的簡單性能，
萬能計算的奇妙想法，
想法是如何萌生，如何在純數學中應用，
美麗的構想線索，把點點與關連串起來。
可記得：唔明唔緊要，只要懂欣賞。
Smartphone智能手機
Click to enlarge (click again to close)
點擊放大(再擊關閉)
A smartphone is a computer, sometimes regarded as an 'electronic brain'. If you are not shocked by this, think again.
Isn't this incredible: something inside your smartphone is busily calculating, doing math, all the time?
Why so many calculations? What are they, and what's the math? Just one thing is calculating, or many things are calculating in union?
The word 'computer' originally means someone who computes, that is, a human calculator.
Throughout history, teams of such computers were employed in the computation of math tables,
for navigators to chart accurate courses,
for engineers to build bridges and railways,
for astronomers to understand the temperature of stars.
Before the 90s, teachers in schools and colleges turned into human computers prior to the end of school year. That was the time when marks from mid-term exam and final exam would be combined by a formula to deliver the yearly marks. Students waited patiently for this 'computer' to stop, to learn their fate in study.
Modern computers do not rely on manpower. Nonetheless, their work is essentially the same: just calculating much faster. What exactly are the things that need a lot of calculations? Using the example of taking a photo with your smartphone,
the raw image captured is computed for reduced storage with minimal data loss,
if the image is edited by rotation or adjustments, there'll be more computation,
the screen display is computed, pixel by pixel in different colors and shades.
If the smartphone is taking a video, there are more computations:
data is computed for compression in storage,
display is computed frame by frame,
sound is computed by phonetic syllables.
When the smartphone is set up with backup to the cloud, think of all the extra computations【B1】!
A computer consists of two parts: software and hardware. Together, a computer takes input, and gives output:
.---------.
| input |
'----+----'
|
v
.----------------------------------------------.
| Software (apps, operating system, etc.) |
| |
| .----------------------------------------. |
| | Hardware (microprocessor, memory, etc.) | |
| | | |
| '----------------------------------------' |
| |
'---------------------+------------------------'
|
v
.--------.
| output |
'--------'
Schematic diagram of a computer.
Your smartphone screen shows a lot of icons. Each icon is an app, short for application, a piece of software. Touching an icon runs an app. The touchscreen serves both as input and output.
Inside your smartphone lies the hardware, the high-tech electronics that run the software.
The most important piece of hardware is the heart of the computer: a microprocessor. Like the human heart, it ticks along, driven by an internal clock. Do you know how fast is the microprocessor clock【C1】?
What is Alan's Turing machine? Well, he was solving a deep problem — a math logic problem. He started from the beginning: how to logically compute 1 + 1 = 2?
This sounds simple. As children we all learn how to do this: show one finger, add one more, then count. However, this is not by logic. This finger-counting method runs into trouble when doing, for example, 17 + 13.
For a logical way, the first thing to realise is this: numbers are just symbols.
There are many ways of using symbols to denote numbers. In fact, the Chinese language uses strokes for simple numbers: 1（一）, 2（二）, 3（三）. Following Alan Turing's thoughts, think of a tape, dividing into squares.
Alan 的圖靈機，到底是什麼？嗯，他正在解決一個深奧的問題 — 數學邏輯問題。他從基本開始：如何邏輯地計算 1 + 1 = 2？
表示數字，使用多種符號。例如，中文用筆劃：1（一）、2（二）、3（三），來表示簡單數字。按照 Alan Turing 的想法，想像一條長紙帶，分成正方格。
To be as simple as possible, just use two symbols: black square or white square.
For the addition 1 + 1 = 2, the start and end can be represented on the tape as:
為求簡單，只需使用兩個符號：黑白方格。加法 1 + 1 = 2 的開始和結束，可以在方格上表示為：
Input:輸入：
representing 1 and 1, to be added.代表兩個1，要相加。
Output:輸出：
representing 2, the result.代表結果2。
To do addition logically is to manipulate symbols, from input to output.
For this, we need to invent a simple 'math brain', and some simple rules.
Alan recalled how his mum taught him to perform long multiplication, e.g. 123 times 456. All he had to do is to use his 'head' to scan symbols, one at a time. Thus the 'math brain' is simply a read/write head: it can read a symbol, write a symbol, then move either left or right along the tape.
Alan 回憶起，媽媽教導如何演算長乘法，例如 123 乘 456。主要動作，是用「頭」掃描符號，逐個逐個。因此，「數學腦」只是個讀寫頭：它會讀符號，寫符號，然後沿著格帶，向左或向右移動。
The action of the read/write head, indicated above by an arrow, can be specified by rules.
Looking at the input and output above for 1 + 1 = 2, let the read/write head start at leftmost,
the head reads black, so invent Rule #1: if head reads ◼, write ◼, move to right.
the head reads white, so invent Rule #2: if head reads ◻, write ◼, move to right.
the head reads black, so another Rule #3: if head reads ◼, write ◻, stop.
But Rule #3 is incompatible with Rule #1: when the head reads ◼, it will not know which rule to follow. However, without Rule #3 but only rules #1 and #2, the head will keep moving towards right, never stops!
Clearly, such a simple setup cannot accomplish this simple task: 1 + 1 = 2. How to recover from such a disaster, and learn something?
What we need is the idea of a state for the machine.
Reading the first ◼ or the second ◼ will put the machine in different states.
The rules will be modified to checking the state for action.
Like doing long multiplication, say multiply 123 and 456, we need to be aware of which digit we are multiplying, so that you can position the partial product properly for later addition.
Alan indicated these various levels of awareness as states, identifying by numbers 1, 2, 3, etc. The machine starts in state 1, changing state as the head moves along the tape. He set state 0 = halt, at which point the machine stops.
turing
tape BWBWW
rule 1 W W R 2
rule 1 B B R 1
rule 2 W B R 0
rule 2 B W L 2
For the simple task of 1 + 1 = 2, we can use two states, as shown above.
The rules are modified to the following form:
At some state, if head reads a symbol, write a symbol, do a move, enter next state.
Click the 'Start' button to step through a simulation of the Turing machine doing this simple task (you'll need a modern browser【*】).
It performs 1 + 1 = 2 using just 2 states and 4 rules: a rule for each state reading either black or white. Most importantly, it stops after 4 steps, printing the desired sum: 2, in symbolic form.
Alan Turing showed that with more symbols, more states, and more rules,
this machine, now called a Turing machine, can handle many different symbolic computations.
For example, for calculation of numbers, we can design one machine to add, another to multiply, or a better machine to perform all arithmetic, etc.
It is really marvelous that a simple design can perform complex computations.
The catch, of course, is that Turing machines are very slow: scanning one square at each step is a very tedious way to compute. However, Alan was thinking about the math. He was interested to figure out, in theory, what is computation. At that time. he had no intention to build a real Turing machine to compute anything.
Alan Turing analysed the operations of his machine by logic, and demonstrated that,
Result #1: With states and rules, a Turing machine can compute anything one can specify.
In fact, a Turing machine is a computer, because it has all the components:
| computer | Turing machine | smartphone |
|-----------|-----------------|------------------------|
| input | tape | touch keyboard |
| software | rules | operating system, apps |
| hardware | head | microprocessor, memory |
| output | tape | touch screen |
In theory, Turing machines are very useful: anything can be computed by states and rules.
In practice, with a head moving along a tape square by square, the machines are extremely inefficient.
不要小覷這麼簡單的機器。
Alan Turing 指出，只要有更多符號、更多狀態和更多規則，這樣的機器（現稱圖靈機），便能處理許多不同符號運算。例如，對於數字計算，可以設計各式機器：一台進行加法，另一台進行乘法，更好的：再一台進行所有算術運算，等等。
Although very useful, the fact that one Turing machine can do only one job following the rules looks like a limitation.
Alan Turing had a flash of insight. He realised that, given a Turing machine,
the number of symbols, states, and rules are all finite, so each can be numbered.
each rule has a fixed format, so each rule can be encoded as marks on the tape.
Hence, why not design a Turing machine that can read such codes, and decode the rules?
Such a machine can following the decoded rules, thus operating exactly as the original Turing machine!
Using the math of logic, Alan constructed such a Turing machine. He called this a universal machine:
Result #2: A universal machine can simulate any Turing machine.
This universal machine is a unique Turing machine. It is also the blueprint of all computers【D1】.
In 1936, Alan Turing published his paper, On Computable Numbers, with an Application to the Entscheidungsproblem.
Computable numbers are numbers that can be computed mechanically, by a Turing machine.
Since a universal machine can simulate any Turing machine,
a universal machine can compute any computable number.
However, when applying logic to analyse the universal machine, Alan Turing found that: there are numbers that cannot be computed by a universal machine. These are called uncomputable numbers.
Entscheidungsproblem is a German word for the Decision Problem. This was first proposed by David Hilbert, a preeminent German mathematician of the 19th and early 20th century. He would like to settle a fundamental problem: is math just a logic game?
If you have played with Sudoku (as shown, solution in【E1】), you'll know that it is a game of logic.
There are nine symbols, which by convention are the digits 1 to 9. Their placements in the grid are determined by logic. A valid Sudoku puzzle can always be solved, by a systematic trial of each possible symbol, although a smart solver can reduce the number of trials by applying certain strategies【E2】.
We may be intimidated when flipping through a math book: there are symbols, lines and lines of them. To us, they look like a language from Mars. To Hilbert, who excelled in all math topics, he could read the math language as we read English, German, or Chinese. Like any language, math consists of a finite number of symbols. Each line of reasoning is just a manipulation of math symbols, according to logical rules followed by all mathematicians.
If David Hilbert knew about Sudoku, he might make the following comparison:
| Sudoku | Mathematics |
|-------------------------------|----------------------------------|
| a logic game of 9 symbols | a logic game of math symbols |
| simple rules for the game | logic rules for inference |
| every puzzle can be solved | every theorem can be proved (?) |
| solution by systemic trials | proof by a systematic method (?) |
The last two are known to be true for Sudoku, but remains unknown for math, thus the question marks. Imagine for once you are a mathematician. Would you hope that those with question marks are true?
A math sentence, before it is known to be true or false, is called a statement.
David Hilbert was convinced that math is a game of logic, and his dream was:
every math statement can be proved true or false, and
a general method to work out the proof can be found.
The first one is the completeness problem, and the second one is the decision problem.
In David Hilbert's mind, the foremost math statement was this one: mathematics has no contradictions. All mathematicians assumed this is true, but he wanted a proof, to give math a firm foundation【E3】.
In general, how to work out a math proof? David Hilbert asked for 'a systemic way', but he didn't clarify exactly what it is. Like Sudoku, perhaps he felt that one way could be trying all possible math symbol combinations, although this would be exceedingly impractical. He was certainly hoping for a better one.
If Hilbert is still alive today, he would have a smartphone. He is hoping for an app that can take a math statement as input, press the 'Prove' button, and outcome the detailed proof【E4】!
During a speech at Königsberg in 1930, David Hilbert, aged 68, concluded that for math, "We must know, we shall know."
Little could David Hilbert predict that, in 1931 Kurt Gödel, a young logician of age 25, showed that, as long as math includes arithmetic, there are math statements that are true but cannot be proved.
Then in 1936, Alonzo Church, an American logician, showed that even when a statement can be proved, there is no general way to generate the proof. In the same year, Alan Turing arrived at the same conclusion, making use of his Turing machines.
These results shattered all the dreams of David Hilbert. Math is more crazy than the math people!
On one hand, since a computing machine can follow any specified method, this shows no machine can produce all math proofs automatically. To produce a tricky proof, most likely some smart ideas are required.
On the other hand, this means a machine can produce some proofs, just don't expect all. Today, there are theorem provers, which are software that can produce simple proofs automatically. For advanced proofs, either the software is tweaked, or some human guidance is required.
On a more practical side, it means there is no general method to detect all computer viruses. A powerful program can detect a lot of viruses, but after a while, a new virus appears that can outsmart the program. The program keeps updating, the virus writers keep getting better.
David Hilbert 幾乎無法預測，就在1931年，25歲的年輕邏輯學家 Kurt Gödel 證明：只要數學包括算術，就必然有是對的數學陳述，但無法證明。
其後在1936年，美國邏輯學家 Alonzo Church 證明：即使定理有證明，也沒有一般的算法，能夠給予證明。同年，Alan Turing 利用他的圖靈機，得出相同的結論。
Today, Alan Turing is recognized as one of the greatest minds of the 20th century【F1】:
His simple Turing machine is the foundation of computer science,
His powerful universal machine is the blueprint of modern computers,
His understanding of machine simulation helps in the codebreaking effort in WWII,
His thoughts on machine and intelligence initiated the study of artificial intelligence (AI),
His work on chemical patterns formation is the basis of morphogenesis in biology.
In summary, Alan Turing conceived a simple idea to solve the deepest math problem. There is beauty seeping through simplicity.
| a simple idea ... | a simple method ... | ... the deepest math problem |
|-------------------------|-------------------------|-----------------------------------|
| Use machine to compute | have states and steps | that's the essence of computation |
A smartphone is a piece of technological beauty: minimal in design, maximal in utility. No wonder it becomes a part of modern life. Yet, the theoretical foundation of such a device is precisely the Turing machine!
Moreover, a smartphone is a piece of technological wonder: holding in your hands is a computer, with hardware inside and software outside. The hand-held device is much more powerful than the on-board computer guiding astronauts landing on the Moon.
Yet conceptually, any computer is just a realisation of the Turing machine!
For more information about him, see my page on Alan Turing.
The page offers another take on Turing machine, universal machine, and the Decision Problem.
The page also has a movie, as well as some books, about Alan Turing.
了解更多有關他的訊息，請參閱我的 Alan Turing 網頁。該頁面從另一角度，探討圖靈機、萬能機和判定問題，還有關於 Alan Turing 的電影和書籍。
Like An Old Friend Comes似是故人來
Click to enlarge (click again to close)
點擊放大(再擊關閉)
The historical movie The Imitation Game (2014), was based on the life story of Alan Turing.
He was homosexual, but he tried to act normal, playing his own 'Imitation Game'.
Alan Turing did propose to Joan Clarke, a female codebreaker in Bletchley Park.
Their relationship did not blossom, as Alan was devoted to his favourite friend Christopher Morcom.
Christopher was his fellow classmate who taught him crytography. Alan regarded Christopher as a talent. but he died without telling Alan his existing illness. Alan was devastated, and vowed to work hard to match the talent of Christopher, as an honour of their friendship.
The script altered some historical details to make up for an enticing story (see link).
Alan built several codebreaking machines called 'Bombes' due to the loud clickering noise,
but in the movie, Alan built only one, and named it Christopher.
At the end of the movie, Joan Clarke came to visit Alan.
Two old friends met, but Alan was no longer his former self after chemical therapy【G1】.
This brings up a 1991 Hong Kong movie, Twin Bracelets, about the mutual love between two village girls.
The story was tragic, and Like An Old Friend Comes is the theme song. The lyricst Albert Leung (林夕, real name 梁偉文), is a famous writer born in Hong Kong.
Being a sensitive subject, Albert Leung wrote the lyrics with only hidden references.
How to be subtle, but not too abstract? He hit upon math.
He made use of double words, units in arithmetic, and units in geometry.
He played tricks on words, using numbers (1, 2, 3, 10, 10000), time (day, month, year), math (dots and lines), nature (wind, rain), and the faraway moon!
2014年的歷史電影《模仿遊戲》，是根據 Alan Turing 的生平故事改編。他是同性戀者，但試圖表現正常，演譯自己的「模仿遊戲」。
的確，Alan Turing 曾向 Bletchley Park 的女密碼破解員 Joan Clarke 求婚。他倆感情並沒有開花，因為 Alan 心儀摯友 Christopher Morcom。Christopher 是他的同窗，曾教他密碼學。Alan 認為 Christopher 是天才，但他去世前沒有告訴 Alan 他的隱疾。Alan 傷心欲絕，發誓要努力向上，與 Christopher 的才華相匹配，作為對他們友誼的致敬。
劇本修改了一些歷史細節，組成一個引人入勝的故事（參見連結）。Alan 建造不只一台密碼破譯機，由於響亮的咔嗒聲，只稱為 Bombe。在電影中，Alan 只建造一台，並命名為 Christopher。電影結束時，Joan Clarke 拜訪 Alan。兩位故人重逢，但 Alan 經過化學治療後，已大不如前【G1】。
In 1936, aged 23, Alan invented his Turing machine, a simple device to crack the hardest math problem.
From Turing machine back to smartphone, we can connect these two dots (點點) by two links (連連), via a critical idea, the computer:
___________
.------------. / / .---------------.
| Smartphone | *----->/ Computer +----->* | Turing Machine |
'------------' /__________/ '---------------'
In the diagram above, you can see dots, links, and 1, 2, 3. I see beauty in the logic behind. You can form your own opinion.
【*】
Modern Browsers
This webpage includes one animation. This feature is supported by modern browsers, which can handle HTML5, SVG and CSS animation (HTML = HyperText Markup Language, SVG = scalable vector graphics, CSS = Cascade Style Sheets). If possible, on your laptop or smartphone, use FireFox or Chrome to view this page.
新一代瀏覽器
此網頁包含動畫。新一代瀏覽器支援這項功能，這些瀏覽器可以處理 HTML5，SVG 和 CSS 動畫（HTML = 超文本標記語言，SVG = 可縮放矢量圖形，CSS = 層疊樣式表）。在筆記本電腦或智能手機上，可以的話，使用 FireFox 或 Chrome 瀏覽此網頁。
【A1】New ₤50 Note Features Alan Turing by Kiona N. Smith, March 31, 2021.
The note features a 1951 photo of Alan Turing, along with his signature, his date of birth written in binary code, and a quote from the mathematician:
This is only a foretaste of what is to come,
and only the shadow of what is going to be.
This quote came from a report in June 1949 “The Times” of London.
Alan Turing was commenting about a Manchester University project which built an electronic calculator Mark I, referred to hyperbolically as a “mechanical mind”.
這張紙幣上有一張1951年 Alan Turing 的照片，以及他的簽名、用二進制代碼寫的出生日期，以及他的一句話：
這只是快要發生之事情的先兆，
並只是將要發生之事情的影子。
這句話出自 1949年6月倫敦《泰晤士報》的一篇報導。Alan Turing 評論曼徹斯特大學的一個項目，該項目建造了 Mark I：一台電子計算機，被誇張地稱為「機械頭腦」。
【A2】
King's Treasures: Turing’s inspiration, posted on July 10, 2015.
When he was just 15½ years old, Alan Turing wrote a précis of The Theory of Relativity by Albert Einstein. In this small memo book, he produced summaries for each chapter of Einstein’s famous work. He did so with the intention of explaining it to his mother.
15歲半時，Alan Turing 撰寫愛因斯坦《相對論》的概要。愛因斯坦著名著作的每一章，他在這本小冊子中作總結。他這樣做，是為了向母親解釋《相對論》。
【B1】
To compute proper connections over the internet, compute check bits to ensure data integrity in transfer, or compute dialogues between computers to ensure error-free data transfer, etc.
要計算正確的互聯網連接，計算校對驗碼字，以確保傳輸數據的完整性。或計算電腦之間對話，以確保數據傳輸無誤，等等。
【C1】
You can find the clock speed of the microprocessor usually in Setting of Device. Most likely it is about 2GHz, that is, 2 giga cycles per second. By the age of 60, you'll have about 2 giga hearbeats. Thus if your heart can beat as fast as 2GHz, you'll fly pass 60 years in one second!
微型處理器的時鐘速度，通常可以在 Device 的 Setting 中找到。最有可能是2GHz左右，即每秒2千兆個循環。人到60歲，會度過大約2千兆的心跳。因此，如果心跳速度，達到 2GHz，你將在一秒鐘內，飛越60載！
【D1】A Non-Technical Guide to Turing Machines by Manuel Brenner, June 22, 2019.
Explains Turing machines to the general public, and how they can help us understand our DNA.
淺易解釋圖靈機，以及它們如何幫助我們了解 DNA。
Click to enlarge (click again to close)
點擊放大(再擊關閉)
【E1】
Solution of the Sudoku puzzle (shown on the right). You can verify this solution in this Sudoku Solver by Chris Fallin. Just copy and paste the number pattern into that page, and click 'Solve' button. See next【E2】.數獨謎題的答案（如右圖所示）。可以在 Chris Fallin 的 Sudoku Solver 中驗證此答案，只需將下列數字模式 copy 並 paste 到該頁面中，然後單擊「Solve」按鈕。參見下一項【E2】。
【E2】Sudoku and Recursive Algorithms by Chris Fallin.
✦Compland✦
Gives the background for the Sudoku solver in 【E1】, by the same author.
Any valid Sudoku puzzle can be solved by a recursive method, called backtracking. Almost any student studying computer science can write a program to solve the Sudoku by backtracking.✦電腦樂園✦
由【E1】同一作者，介紹 Sudoku solver 的背景。
任何有解的數獨謎題，都可以通過遞歸方式解決，稱為「回溯算法」（backtracking）。電腦科學的學生，大都能夠編寫程式，通過回溯算法，解決數獨謎題。
【E3】
David Hilbert did some work in this direction, showing that geometry has no contradiction if arithmetic has no contradiction. Since algebra is developed from arithmetic, and all math stands on the two pillars of geometry and algebra, his dream will be fulfilled when arithmetic itself can be shown to have no contradiction.
David Hilbert 在這個方面下了功夫，說明如果算術沒有矛盾，幾何就沒有矛盾。由於代數是 從算術發展而來，而所有數學，都建立在兩大支柱：幾何和代數；因此，如果算術本身沒有矛盾，他的夢想就會實現。
【E4】
Need a proof when the math statemenat is true, and a disproof when the math statement is wrong. A disproof can be very short, just a counter-example is enough.
當數學陳述為對時，要有證明。當數學陳述為錯時，只有反證。反證可以很短，一個反例已足夠。
【F1】Codebreaker: Alan Turing's Life and Legacy【5:13】cc
This is an exhibition in Science Museum, London, from June 2012 to Ocotber 2013.
Codebreaker celebrated the centenary of the birth of British mathematician and computer pioneer Alan Turing.
At the heart of the exhibition was the pilot ACE (Automatic Computing Engine) computer, built to Turing’s ground-breaking design. It is the most significant surviving Turing artefact and is now on display in the Information Age gallery. 2012年6月至2013年10月，倫敦科學博物館舉辦 Codebreaker 展覽，慶祝英國數學家和計算機先驅艾倫·圖靈（Alan Turing）誕辰一百週年。展覽的核心是 ACE（Automatic Computing Engine，自動計算引擎）計算機的試點模型，按照圖靈的突破性設計打造。它是現存最重要的圖靈製成品，在「訊息時代」畫廊展出。
【G1】Alan Turing's break down scene | The Imitation Game【4:04】cc
Two friends reunite at the last part of the movie "The Imitation Game".電影《模仿遊戲》的末段，兩位故人重逢。
Click to enlarge (click again to close)
Click to enlarge (click again to close)
Click to enlarge (click again to close)
Click to enlarge (click again to close)
Click to enlarge (click again to close)
