Shadowing Practice: Turing & The Halting Problem - Computerphile - Learn English Speaking with Video

בחר מצב תרגול

כל מצב פותח חדר תרגול במסך מלא.

81 משפטים

אם המשפטים קצרים או ארוכים מדי, לחץ על ערוך כדי להתאים אותם.

Today we're going to be talking about a problem in logic, and how in solving that problem,

Alan Turing almost inadvertently invented the modern digital computer.

So we start back at the beginning of the 20th century, where mathematicians had posed this problem.

- Thank you.

In logic, we're interested in finding, do these premises entail this conclusion?

So premises are the bits you start off with in an argument.

They are the bits you know at the beginning or your assumptions.

And the conclusion is the bit you want to establish, the bit that you reason to with your argument.

And we want to know, is there a test that will tell us, yes, for sure, these premises do or don't entail this conclusion?

Is there an automatic way of finding out whether they do or whether they don't. So that's the problem.

It's called the decision problem.

and mathematicians wanted to find out Is there an answer to the decision problem for first order logic?

That's the kind of logic you learn in philosophy or mathematics at university.

So lots of mathematicians were trying to work out, is first order logic decidable?

That is, can we automatically test whether the premises entail the conclusion?

Alan Shuring was one of the first to discover that first order logic isn't decidable.

I To prove this, It's really difficult conceptually,

because you have to be able to show no possible program can give you the answer.

But how do you do that?

How do you show something about every possible program?

You can't run through every program one by one.

But Turing came up with a brilliant solution.

Yeah.

His idea goes something like this.

Suppose we have a program and let's just draw it as a black box.

It's going to take some inputs, and it's going to give us some outputs.

our program is going to solve some problem.

a problem like, do the premises entail the conclusion?

We ask it a question and it will give us an answer: yes, or no?

Now here's another question we can ask: Thank you.

Let's look at all of those possible programs.

And we're just thinking of them as black boxes at the moment.

We might want to know, is this program Given a certain input, gonna give us an answer.

Or is it going to trundle on forever and never give us an answer?

That is, is it going to halt or is it not going to halt eventually?

So think about your computer running.

You want it to give you an answer.

And whether it's a good answer or a bad answer, it's better than no answer.

No answer would mean the computer trundles round forever and ever in a loop.

And you would just never know whether it's going to finish today, tomorrow or never.

So halting is good.

So there's another question we can ask: Given some program and some inputs, will it ever halt?

Now it turns out that our logical problem Do these premises entail this conclusion?

is very similar to this halting problem.

In fact, if we can solve the logical problem, then we can solve the halting problem.

Will this program halt on this input?

So the clever part of Turing's proof is to show that it's impossible for any machine, however clever it is, to solve the halting problem.

That is to tell us whether a given machine with a given input will halt or not.

And here's how we did it.

Let's suppose we've got a machine or a program that solves the problem for us it solves the holding problem.

Don't worry about how it works, let's just think of it as a black box, taking a description of a machine and an input, and giving us an answer.

Yes it will halt or no it won't halt.

Just suppose that's possible.

Call that machine H for the halting problem.

If you give me that machine, I can transform it into a different machine like this.

I stick some extra bits on it so that If it gives me a yes answer, I make it loop forever without ever stopping.

If it gives me a no answer on the other hand, it's gonna halt straight away.

Let's call that big machine the whole thing.

H plus.

Now here's another question we can ask: what happens if I feed the whole machine into itself.

So I'm going to put H plus Thank you in here and H + in here.

So the question I'm now asking is, I'm feeding H + into itself.

So I'm asking the question: Does H + halt?

give an input H+.

And here's where it all goes wrong.

because If H + does halt, We get a yes answer.

But then it loops forever, so it doesn't halt.

On the other hand, if it doesn't halt, We get a no answer, but then it halts.

So if it does halt, then it doesn't halt.

But if it doesn't halt, then it does halt.

Either way, we get a contradiction.

It's a paradox.

And what that shows is we started off assuming that we can solve the problem.

we've ended up with a paradox.

So our assumption was bad.

It turns out there's no possible machine, no possible program that solves the halting problem.

The really clever bit about Turing's idea is it doesn't matter what kind of program or machine it is.

It doesn't matter whether it's An abstract algorithm, whether it's a real computer, a physical computer, it doesn't matter what it is.

We've proved that no such program is possible.

you Turing, as part of his argument, had to say a little bit about what's going on in these black boxes.

And the idea is that every card represents an instruction in this Turing machine.

הורד אפליקציה

כל מה שאתה צריך כדי לדבר בשטף

הגיית AIציון לכל משפט

תרגול IPAשלוט בכל צליל

אוצר מיליםבנה את מאגר המילים שלך

משחק אוצר מיליםלמד תוך כדי משחק

סרוק QR

Download on theApp Store Get it onGoogle Play

אותו ערוץ

Why AI Tokens are so Expensive - Computerphile

Daily ConversationUniversity StudentsWorking Adults

FOR YOU

המלץ על סרטון

136 משפטים

Vocabulary and speaking notes for this lesson

This video has 81 sentences and 976 words to shadow. The speech runs for 6:14. The speaker talks at a natural 157 words per minute, close to everyday conversation. 83% of the words are among the 3,000 most common in English; the rest is worth studying before you start.

Key vocabulary in this video

15 words from the video worth learning, with pronunciation and meaning:

Word	Pronunciation	Meaning
hungry adjective	/ˈhʌŋ.ɡɹi/	Affected by hunger; having the physical need for food.
solve verb	/sɒlv/	To find an answer or solution to a problem or question; to work out.
input noun	/ˈɪnpʊt/	The act or process of putting in; infusion.
conclusion noun	/kənˈkluːʒən/	The end, finish, close or last part of something.
premise noun	/ˈpɹɛm.ɪs/	A proposition antecedently supposed or proved; something previously stated or assumed as the basis of further argument; a condition; a supposition.
loop noun	/luːp/	A length of thread, line or rope that is doubled over to make an opening.
clever adjective	/ˈklɛv.ɚ/	Nimble with hands or body; dexterous; skillful; adept.
logical adjective	/ˈlɑd͡ʒɪkəl/	In agreement with the principles of logic.
assumption noun	/əˈsʌm(p).ʃ(ə)n/	The act of assuming, or taking to or upon oneself; the act of taking up or adopting.
paradox noun	/ˈpæ.ɹəˌdɒks/	An apparently self-contradictory statement, which can only be true if it is false, and vice versa.
establish verb	/ɪˈstæb.lɪʃ/	To make stable or firm; to confirm.
output noun	/ˈaʊtpʊt/	Production; quantity produced, created, or completed.
discover verb	/dɪˈskʌvə/	To find or learn something for the first time.
automatic adjective	/ˌɔː.təˈmæt.ɪk/	Capable of operating without external control or intervention.
mathematics noun	/mæθ(.ə)ˈmæt.ɪks/	An abstract representational system studying numbers, shapes, structures, quantitative change and relationships between them.

Phrasal verbs you will hear

Word	Pronunciation	Meaning
find out verb		To discover, as by asking or investigating.
turn out verb		To end up; to result.
come up with verb		To manage to produce, deliver, or present (something) by inventing, creating, thinking of, or obtaining it.
run through verb		To summarise briefly.
start off verb		To begin.
work out verb	/ˌwɝk ˈaʊt/	To calculate.

Pronunciation to watch

The speaker uses 25 contractions and reduced forms, such as doesn't, I'm, don't. Say them the short way, as you hear them.

The “th” sounds: mathematics /mæθ(.ə)ˈmæt.ɪks/, algorithm /ˈælɡəɹɪðm̩/, mathematician /ˌmæθ.(ə.)məˈtɪʃ.ən/
The “sh” and “zh” sounds: conclusion /kənˈkluːʒən/, assumption /əˈsʌm(p).ʃ(ə)n/, establish /ɪˈstæb.lɪʃ/, instruction /ɪnˈstɹʌkʃən/, mathematician /ˌmæθ.(ə.)məˈtɪʃ.ən/
Long words — get the stress right: automatic /ˌɔː.təˈmæt.ɪk/, mathematics /mæθ(.ə)ˈmæt.ɪks/, mathematician /ˌmæθ.(ə.)məˈtɪʃ.ən/, decidable [dɪˈsaɪdəbəɫ], conceptually /kənˈsɛp.tjʊə.li/

How to practise with this video

Listen to the whole video once without speaking and note the words you do not know.
Start at 0.75× speed, shadow it sentence by sentence, then go back to normal speed once it feels easy.
Record yourself and compare with the original, paying attention to words like hungry, solve, input.

מהי טכניקת השאדואינג?

שאדואינג היא טכניקת למידת שפה מבוססת מדע שפותחה במקור להכשרת מתורגמנים מקצועיים ופופולרית על ידי הפוליגלוט ד"ר אלכסנדר ארגואלס. השיטה פשוטה אך עוצמתית: אתה מקשיב לאודיו באנגלית ילידית וחוזר עליו בקול רם מיד — כמו צל העוקב אחרי הדובר עם עיכוב של 1–2 שניות בלבד. בניגוד להאזנה פסיבית או תרגילי דקדוק, שאדואינג מכריח את המוח והשרירים בפה לעבד ולשחזר דפוסי דיבור אמיתיים בו זמנית. מחקרים מראים שזה משפר משמעותית את דיוק ההגייה, האינטונציה, הקצב, הדיבור המחובר, הבנת השמיעה ושטף הדיבור — מה שהופך אותו לאחת השיטות היעילות ביותר להכנה לIELTS Speaking ולתקשורת באנגלית בעולם האמיתי.

טכניקת Shadowing: קרא את המדריך המלא שלב אחר שלב →

Shadowing Practice: Turing & The Halting Problem - Computerphile - Learn English Speaking with Video

בחר מצב תרגול

הורד אפליקציה

Why AI Tokens are so Expensive - Computerphile

Early Computing: Crash Course Computer Science #1

【TED】優れたリーダーはどうやって行動を促すか/サイモン・シネック （日本語字幕）

AI Will End Philosophy, Physicist Claims

[C1] Stop Overthinking | English Listening & Speaking Practice

What is clean code? - Uncle Bob

The Map of Mathematics

CAP Theorem in System Design Interviews

Exposing The Flaw In Our Phone System

We Let $200 GPT-Pro Think for 7 Days on Unsolved Math

The Science of Thinking

The Human Economy in the Age of AI | Ben Pascut | TEDx

🚫 Java Deadlock Explained: Why Your Code is Stuck 😱 (Beginners Must Watch!)