Alan Turing: Crash Course Computer Science #15
Summary
TLDR本视频介绍了计算机科学之父艾伦·图灵的生平和成就。图灵在剑桥大学攻读硕士期间,提出了解决德国数学家大卫·希尔伯特提出的“决策问题”的方法,即是否存在一个算法,能够对形式逻辑中的陈述给出始终准确的“是”或“否”答案。图灵提出了一种理论计算模型——图灵机,它虽然简单,但功能强大,与λ演算在计算能力上等价。图灵机通过无限长的纸带、读写头和一系列规则来模拟任何计算过程。图灵还探讨了著名的“停机问题”,证明了不存在一个算法能够确定任意程序是否会无限运行。在第二次世界大战中,图灵设计了一种名为“Bombe”的电子计算机,帮助破解了德国的恩尼格玛密码机,对战争胜利起到了关键作用。战后,图灵对人工智能领域做出了贡献,提出了著名的“图灵测试”。然而,由于当时对同性恋的法律迫害,图灵的生活悲剧性地结束。图灵的贡献被广泛认可,图灵奖就是以他的名字命名的计算机科学领域的最高荣誉。
Takeaways
- 👨💻 艾伦·图灵被誉为计算机科学之父,对现代计算理论有着深远的影响。
- 🧮 图灵在剑桥大学攻读硕士期间,首次接触了我们现在称之为计算机科学的问题,特别是希尔伯特的“决策问题”。
- ✅ 阿隆佐·丘奇和图灵分别独立提出了λ演算和图灵机,两者在计算能力上是等价的,但图灵机因其简单性更受欢迎。
- 📜 图灵机是一个理论计算模型,由无限长的纸带、读写头、状态寄存器和规则组成。
- 🔢 图灵机通过简单的规则可以模拟任何计算过程,证明了理论上的可能性,即所谓的“通用计算机”。
- 🔍 图灵在解决希尔伯特的决策问题时,提出了停机问题,并通过逻辑悖论证明了停机问题是不可解的。
- 🏆 图灵的成就不仅限于理论,他在第二次世界大战中对破译德国密码机“恩尼格玛”做出了重大贡献。
- 💻 图灵设计了一种名为“Bombe”的电子机械计算机,利用了恩尼格玛机的缺陷,极大地提高了破解效率。
- 🏛️ 战后,图灵继续在学术界工作,并对早期电子计算机的发展做出了贡献。
- 🧠 图灵对人工智能领域也有重要贡献,提出了著名的“图灵测试”,用以判断计算机是否能够展现出与人类不可区分的智能。
- 📛 图灵的个人生活悲剧与他的科学成就同样著名,他因同性恋倾向在当时的英国受到迫害,并最终选择了自杀。
- 🏅 图灵奖是计算机科学领域的最高荣誉,以艾伦·图灵的名字命名,表彰他在计算机科学上的巨大贡献。
Q & A
艾伦·图灵是如何对现代计算机科学产生影响的?
-艾伦·图灵提出了许多理论概念,包括图灵机,这些概念为现代计算奠定了基础。图灵机提供了一个简单而强大的计算数学模型,与λ演算在计算能力上等价,但因其相对简单性,在计算机科学领域更受欢迎。
图灵机是如何工作的?
-图灵机是一种理论计算设备,它有一个无限长的存储带,用于存储符号,一个读写头可以读取、写入或修改存储带上的符号,还有一个状态变量来存储关于机器当前状态的信息,以及一组规则描述机器的行为。给定一个状态和当前符号,规则可以决定写入符号、改变机器状态、移动读写头,或者这些动作的任意组合。
什么是图灵完备性?
-图灵完备性是指一个系统能够执行任何计算,只要有足够的时间和内存。如果一个计算机或编程语言是图灵完备的,那么它就和图灵机一样强大,能够模拟任何计算机的计算过程。
艾伦·图灵是如何帮助解决二战中的密码破译问题的?
-艾伦·图灵设计了一种特殊的电子机械计算机——Bombe,利用了恩尼格玛机的一个关键缺陷(即一个字母永远不会被加密成它自己),通过尝试大量可能的设置组合,排除那些会导致字母自我加密的设置,从而大大缩小了可能的恩尼格玛机设置数量。
什么是图灵测试?
-图灵测试是由艾伦·图灵提出的一种测试,旨在判断计算机是否能够展现出与人类不可区分的智能。如果一个人在与两个对话者(一个是人类,一个是计算机)通过文字交流时,无法区分哪个是计算机,那么计算机就通过了图灵测试。
艾伦·图灵的个人生活对他有什么影响?
-艾伦·图灵是同性恋者,但在当时,同性恋在许多地方是非法的。1952年,一次对他家的盗窃调查揭露了他的性取向,导致他被控以严重猥亵罪。图灵选择了缓刑和激素治疗以避免监禁,但这些治疗改变了他的情绪和个性。普遍认为,图灵在1954年因服用毒药自杀,享年41岁。
图灵奖是什么?
-图灵奖是计算机科学领域的最高荣誉,相当于物理学、化学或其他科学领域的诺贝尔奖。它是为了纪念艾伦·图灵对理论计算机科学的贡献而设立的。
大卫·希尔伯特提出的决策问题是什么?
-大卫·希尔伯特提出的决策问题(Entscheidungsproblem)询问是否存在一个算法,它可以接受一个用形式逻辑写成的语句作为输入,并总能产生一个准确无误的“是”或“否”答案。
Lambda Calculus 是什么?
-Lambda Calculus 是一种数学表达式系统,由美国数学家阿隆佐·丘奇开发,用以解决决策问题。它能够表示任何计算,但数学技术难以应用和理解。
艾伦·图灵是如何证明停机问题的不可解性的?
-艾伦·图灵通过设计一个思想实验,即一个能够判断其他程序是否会停机的图灵机(命名为H),然后构建了另一个图灵机(命名为Bizzaro),它的行为与H相反。当Bizzaro用自身的描述作为输入时,会导致一个悖论,从而证明了停机问题是不可解的。
为什么说图灵机是通用计算机的模型?
-图灵机被认为是通用计算机的模型,因为它们能够模拟任何计算过程,只要给定足够的时间和内存。这意味着,理论上,一个图灵机可以通过改变其规则和输入,来执行任何计算机程序的功能。
图灵在普林斯顿大学完成了什么?
-艾伦·图灵在普林斯顿大学完成了他的博士学位,期间他在阿隆佐·丘奇的指导下学习。
Outlines
😀 计算机科学之父艾伦·图灵的生平与贡献
本段介绍了艾伦·图灵的生平和对计算机科学的贡献。图灵是计算机科学理论概念的奠基人,他提出了图灵机的概念,解决了希尔伯特的“决策问题”,并证明了不存在一个通用算法能够解决所有数学问题。图灵机是一个理论计算模型,具有无限的存储带和读写头,能够执行简单的计算任务。图灵还对密码学做出了贡献,特别是在第二次世界大战中破解了德国的恩尼格玛密码机。
🧠 图灵的图灵机与停机问题
这一段深入探讨了图灵机的功能和停机问题。图灵机是一个简单的理论计算模型,能够执行任何计算,只要有足够的时间和内存。图灵利用图灵机解决了希尔伯特的决策问题,特别是停机问题,即无法确定一个程序是否会无限运行。他通过逻辑上的悖论证明了停机问题是不可解的,表明了计算机能力的局限性。
🏆 图灵的人工智能贡献与个人悲剧
最后一段讲述了图灵在人工智能领域的贡献以及他的个人生活。图灵预见了计算机能够展现出与人类不可区分的智能,并提出了图灵测试,即如果一台计算机能在对话中让人无法区分它与人类的差别,则该计算机可以被认为是智能的。此外,还提到了图灵的个人悲剧,他因为同性恋倾向在当时的英国受到法律的迫害,最终选择了自杀。图灵的贡献被广泛认可,图灵奖就是以他的名字命名的计算机科学领域的最高荣誉。
Mindmap
Keywords
💡计算机科学
💡艾伦·图灵
💡图灵机
💡可计算性
💡停机问题
💡恩尼格玛机
💡图灵测试
💡Lambda 演算
💡大卫·希尔伯特
💡普林斯顿大学
💡图灵奖
Highlights
艾伦·图灵被认为是计算机科学之父,他提出了许多现代计算理论概念。
图灵在1935年作为剑桥大学国王学院的硕士生时,开始研究德国数学家大卫·希尔伯特提出的“决策问题”。
美国数学家阿隆佐·丘奇首先提出了这个问题的解决方案,发展了一种称为Lambda Calculus的数学表达式系统。
图灵提出了一种假想的计算设备——图灵机,它提供了一个简单而强大的计算数学模型。
图灵机具有无限长的存储带和读写头,能够读取、写入或修改带上的符号。
图灵机通过一系列规则来描述机器的行为,包括写符号、改变状态和移动读写头。
图灵机通过简单示例展示了如何计算一串以零结尾的一的个数是否为偶数。
图灵机证明了任何计算都可以由足够时间和内存的图灵机完成,这表明了图灵机作为一个计算模型的强大。
图灵机的模型证明了没有计算机比图灵机更强大,所有现代计算系统都是图灵完备的。
图灵通过图灵机研究了“停机问题”,即是否存在一个算法可以确定图灵机会不会永远运行下去。
图灵证明了停机问题是不可解的,通过逻辑上的矛盾来展示这一点。
图灵在普林斯顿大学完成了他的博士学位,并在第二次世界大战期间将他的才华应用于战争努力。
图灵设计了一种名为“Bombe”的专门用途的电子计算机,利用了恩尼格玛机的一个关键缺陷来破解密码。
图灵和他在布莱切利公园的同事们不懈地努力,对抗德国的加密机制,为盟军在多个战场上提供了优势。
战后,图灵回归学术界,并对早期的电子计算工作做出了贡献,如曼彻斯特马克1型计算机。
图灵对人工智能领域做出了著名贡献,提出了图灵测试,即如果计算机能够欺骗人类认为它是人,则该计算机应被视为智能的。
图灵的个人生活与悲剧紧密相连,他在同性恋行为在联合王国和世界大部分地区非法的时代是同性恋者。
图灵因同性恋行为被定罪,并选择荷尔蒙治疗以继续他的学术工作,但这种治疗改变了他的情绪和个性。
图灵在1954年以41岁的年龄结束了自己的生命,他的去世被广泛认为是自杀。
图灵因其对理论计算机科学的贡献而有许多以他的名字命名的事物,其中最负盛名的是图灵奖,相当于计算机科学领域的诺贝尔奖。
Transcripts
Hi, I'm Kerry Ann and welcome to Crash Course computer science.
Over the past few episodes, we've been building up our understanding of computer science
fundamentals, such as functions, algorithms and data structures.
Today, we're going to take a step back and
look at the person who formulated many of the theoretical concepts that underline modern computation.
The father of computer science and not quite Benedict Cumberbatch lookalike Alan Turing.
[Crash Course intro playing]
Alan Mathison Turing was born in London in 1912
and showed an incredible aptitude for maths and science throughout his early education.
His first brush of what we now call computer science came in 1935 while he was a master's student at King's College in Cambridge.
He set out to solve a problem posed by German Mathematician David Hilbert known as the Entscheidungsproblem
or decision problem, which asked the following:
is there an algorithm that takes as input a statement written in formal logic, and
produces a "yes" or "no" answer that's always accurate?
If such an algorithm existed,
we could use it to answer questions like, "Is there a number bigger than all numbers?"
No, there's not. We know the answer to that one,
but there are many other questions in mathematics that we'd like to know the answer to.
So if this algorithm existed, we'd want to know it.
The American mathematician Alonzo Church first presented a solution to this problem in 1935.
He developed a system of mathematical expressions called Lambda Calculus
and demonstrated that no such universal algorithm could exist.
Although Lambda Calculus was capable of representing any computation,
the mathematical technique was difficult to apply and understand.
At pretty much the same time on the other side of the Atlantic,
Alan Turing came up with his own approach to solve the decision problem.
He proposed a hypothetical computing machine, which we now call a Turing Machine.
Turing Machines provided a simple, yet powerful
mathematical model of computation.
Although using totally different mathematics,
they were functionally equivalent to lambda calculus in terms of their computational power.
However their relative simplicity made them much more popular in the burgeoning field of computer science.
In fact, they're simple enough that I'm going to explain it right now.
A Turing Machine is a theoretical
computing device equipped with an infinitely long memory tape which stores symbols
and a device called a read/write head which can read and write, or
modify, symbols on that tape.
There's also a state variable in which we can hold a piece of information
about the current state of the machine.
And a set of rules that describes what the machine does.
Given a state and the current symbol the head is reading,
the rule can be to write a symbol on the tape change the state
of the machine move the read/write head to the left or right by one spot or any
combination of these actions.
To make this concrete let's work through a simple example:
a Turing Machine that reads a string of ones ending in a zero and
computes whether there is an even number of ones. If that's true
The machine will write a one to the tape and if it's false, it'll write a zero. First
We need to define our Turing machine rules. If the state is even and the current symbol of the tape is one,
then we update the machine state to odd and move the head to the right. On the other hand if the state is even and
The current symbol is zero, which means we've reached the end of the string of ones, then we write one to the tape and change
the state to halt, as in we're finished and the Turing machine has completed the
computation. We also need rules for when the Turing machine is in an odd state,
one rule for the symbol on the tape is a zero and another for when it is one.
Lastly we need to define a
Starting state, which we'll set to be even. Now we've defined the rules in the starting state of our Turing machine,
which is comparable to a computer program, we can run it on some example input. Let's say we store 1 1 0 onto tape.
That's two ones which means there is an even number of ones, and if that's news to you,
We should probably get working on crash course Math.
Notice that our rules only ever move their head to the right so the rest of the tape is irrelevant.
We'll leave it blank for simplicity. Our Turing machine is all ready to go so let's start it. Our state is even and the first
number we see is a one. That matches our topmost rule
and so we execute the effect, which is to update the state to odd and move the read/write head to the right by one spot.
Okay, now we see another one on the tape
But this time our state is odd
and so we execute our third rule which sets the state back to even and moves the head to the right. Now
we see a 0 and our current state is even so we execute our second rule
which is to write a 1 to the tape signifying that yes, it's true,
there is an even number of ones, and finally the machine halts.
That's how turing machines work pretty simple right so you might be wondering why there's such a big deal
Well cheering shows that this simple hypothetical machine can perform any computation if given enough time and memory
It's a general-purpose computer our program was a simple example
But with enough Rules states and tape you could build anything - a web browser, world of warcraft - whatever! Of course it would be
ridiculously inefficient, but it is theoretically possible.
And that's why, as a model of computing, it's such a powerful idea.
In fact in terms of what it can and cannot compute
there's no computer more powerful than a turing machine. A computer that is as powerful is called Turing complete
Every modern computing system your laptop your smartphone and even the little computer inside your microwave and thermostat are all Turing Complete.
To answer Hilbert's decision problem, Turing applied these new Turing machines to an intriguing
computational puzzle: the halting problem. Put simply this asks
"Is there an algorithm that can determine, given a description of a turing machine and the input from its tape,
whether the Machine will run forever or halt?" For example we know our Turing machine will halt when given the input 1 1 0
Because we literally walk through the example until it halted, but what about a more complex problem?
Is there a way to figure out if the program will halt without
executing it? Some programs might take years to run
so it would be useful to know before we run it and wait and wait and wait and then start getting worried and wonder and
Then decades later when you're old and gray control-alt-delete so much sadness
Unfortunately turing came up with a proof that shows the halting problem was in fact unsolvable, through a clever logical contradiction.
Let's Follow his reasoning. Imagine
we have a hypothetical Turing machine that takes a description of a program and some input for his tape and always outputs either
Yes, it halts or no, it doesn't and I'm going to give this machine a fun name
H for Holtz. Don't worry about how it works. Let's just assume such a machine exists
We're talking theory here. Turing reasoned if there existed a program
Whose halting behavior was not decidable by age it would mean the halting problem is
Unsolvable to find one Turing designed another Turing machine that built on top of H. If H says the program holds
Then we'll make our new machine loop forever. If the answer is no
It doesn't halt, we'll have the new machine output a no and halt. In essence
We're building a machine that does the opposite of what H says: halt if the program doesn't halt and run forever if the program halts
For this argument we'll also need to add a splitter to the front of our new machine
So that it accepts only one input and passes that as both the program and input into H. Let's call this new machine "Bizzaro"
So far this seems like a plausible machine, right?
Now it's going to get pretty complicated
But bear with me for a second. Look what happens when you pass Bizzaro a description of itself as the input
This means we're asking H what Bizzaro will do when asked to evaluate itself
But if H says Bizzaro halts then Bizzaro enters its infinite loop and thus doesn't halt
And if H says Bizarro doesn't halt then Bizzaro outputs a no and halts
so H can't possibly decide the halting problem correctly because there is no answer. It's a paradox and this paradox means
That the halting problem cannot be solved with Turing machines. Remember Turing proved that Turing machines could implement any computation
So this solution to the halting problem proves that not all problems can be solved by computation. Wow, that's some heavy stuff
I might have to watch that again myself.
Long story short Church
and Turing showed there were limits to the ability of computers no matter how much time or memory you have there are just some problems
that cannot be solved ever.
At this point in
1936 Turing was only 24 years old and really only just beginning his career. From 1936 through
1938 he completed a PhD at Princeton University
under the guidance of Church then after graduating he returned to Cambridge.
Shortly after in
1939 Britain became embroiled in World War II Turing's genius was quickly applied to the war effort. In fact a year before the war
Started he was already working part-time at the uk's government code and Cypher school
Which was the British code breaking group based out of Bletchley Park. One of his main efforts was figuring out how to decrypt German communications
Especially those that use the enigma machine. In short these machines scrambled text. Like you'd type the letters
H-E-L-L-O
and the letters XWDBJ
Would come out. This process is called encryption
The scrambling wasn't random. The behavior was defined by a series of re-orderable rotors on the top of the enigma machine
Each with 26 possible rotational positions. There was also a plug board at the front of the machine that allowed pairs of letters to be swapped
In total there were billions of possible settings. If you had your own enigma machine and you knew the correct rotor and plug board settings
You could type in XWDBJ
and hello would come out. In other words, you decrypted the message
Of course the German military wasn't sharing their enigma settings on Social Media
So the allies had to break the code with billions of Rotor and plug board combinations
There was no way to check them all by hand
Fortunately for Turing, enigma machines and the people who operated them were not perfect
Like one key flaw was that a letter would never be encoded as itself as in an h was never encrypted as an h
Turing, building on earlier work by Polish code breakers, designed a special-Purpose
electromechanical
Computer called the Bombe that took advantage of this flaw. It tried lots and lots of combinations of enigma settings
for a given encrypted message if the Bombe found a setting that led to a letter being encoded as itself
Which we know the real Enigma machine couldn't do, that combination was discarded then the machine moved on to try another combination
So Bombes were used to greatly narrow the number of Possible enigma settings
This allowed human code breakers to hone their efforts on the most probable solutions
Looking for things like common german words in fragments of decoded text
Periodically the Germans would suspect someone was decoding their communications and upgrade the enigma machine like they'd add another rotor creating many more combinations
they even built entirely new encryption machines. Throughout the war Turing and his colleagues at bletchley park worked tirelessly to defeat these mechanisms and
overall the intelligence gained from Decrypted German communications
Gave the allies an Edge in many theatres with some historians arguing it shortened the war by years
after the war turing returned to Academia and
Contributed to many early electronic computing efforts like the Manchester Mark 1 which was an early and influential stored-Program computer
But his most famous post-war contribution was to artificial intelligence, a field so new that it didn't even get that name until 1956
It's a huge topic
So we'll get to it again in future episodes
In 1950 Turing could envision a future where computers were powerful enough to exhibit intelligence equivalent to or at least
indistinguishable from that of a human
Turing postulated that a computer would deserve to be called intelligent
If it could deceive a human into believing that it was human. This became the basis of a simple test now called the turing test
Imagine that you are having a conversation with two different people not by voice or in person
But by sending typed notes back and forth. You can ask any questions you want and you get replies
But one of those two people is actually a computer. If you can't tell which one is human and which one is a computer then
the computer passes the test
There's a modern version of this test called a completely automated public turing test to tell computers and humans apart or captcha for short
These are frequently used on the internet to prevent automated systems from doing things like posting spam on Websites. I'll admit sometimes
I can't read what those squiggly things say. Does that mean I'm a computer? Normally in this series
We don't delve into the personal lives of these historical figures
But in Turing's case his name has been inextricably tied to tragedy so his story is worth mentioning
Turing was gay in a time when homosexuality was illegal in the united Kingdom and much of the world. An investigation into a 1952 Burglary
at his home revealed his sexual orientation to the authorities who charged him with gross indecency. Turing was convicted and given a choice between
Imprisonment or probation with hormonal treatments to suppress his sexuality
He chose the latter in part to continue his academic work, but it altered his mood and personality
Although the exact circumstances will never be known, it's most widely accepted that Alan Turing took his own life by poison in 1954
He was only 41. Many things have been named in recognition of Turing's contributions to theoretical computer science
But perhaps the most prestigious among them is the turing award the highest distinction in the field of computer science
Equivalent to a nobel prize in Physics, chemistry or other sciences. Despite a life cut short
Alan inspired th e first generation of computer scientists and laid key groundwork that enabled a digital era we get to enjoy today
I'll see you next week. Crash course computer science is produced in association with PBS digital studios at their channel
You can check out our pla ylist to show like gross science
ACS reactions and the art assignment. this episode was filmed at the Chad and stacey Emigholz studio in Indianapolis, Indiana
And it was made with the help of all these nice people and a wonderful graphics team thought cafe
Thanks for watching and try turning it off and then back [on] again
تصفح المزيد من مقاطع الفيديو ذات الصلة
5.0 / 5 (0 votes)