0:04

So, let's take a look now at implications of the undecidability of the halting problem.

Â I think the main thing that

Â people should take away is that if you know that a problem is undecidable,

Â don't try to solve it.

Â Here's Alice and Bob.

Â Say, Alice, we came up with an idea at our hackathon.

Â We're going to go for startup. So what's the idea?

Â Well, we're going to have an app that you can use to

Â make sure that any app you download won't hang your phone?

Â Alice who has taken a few computer science courses says,

Â well, I think that's undecidable.

Â Bob really doesn't know quite what that means so maybe a better way to phrase it is,

Â what happens if you give your app itself?

Â That's the self reference part that really

Â characterizes not computer ability or undecidability.

Â And let's take a look at some implications.

Â If you really think about it,

Â this idea is the reason that it's difficult to

Â debug programs because all the following things are undecidable.

Â Halting problem is something that every beginning programmer would like to solve.

Â As soon as you learn about loops and as soon as you

Â have your first program go into an infinite loop,

Â you wonder why doesn't my instructor have a program that takes

Â my program as input and checks whether or not it's got an infinite loop?

Â You can't, because the undecidability of the halting problem.

Â What would that program do if it was given itself as input?

Â And so forth and so on without much trouble you get back to Turing's proof.

Â And then there's lots of similar problems that

Â with similar types of constructions can be proved to be undecidable.

Â The idea is to assume that you can

Â solve the halting problem then you can solve this problem.

Â But since the halting problems

Â undecidable that would mean that this problem is undecidable.

Â So, these types of things.

Â Given a function does it halt on every input X?

Â Given a function with no input, does it halt?

Â Do two functions always return the same value?

Â That's another one that every programmer would like to have.

Â I have a new version of an old program and I want to know if it does the same thing.

Â And you might go and get a job in the software industry and have

Â a manager ask you to write up something like this and you can say,

Â no, I can't do it.

Â It's undecidable.

Â And all kinds of things and programming systems.

Â So, did I declare a variable and then use it without initializing it?

Â Again, undecidable.

Â I have a huge programming system,

Â there's lots of code in there,

Â does every line of code going to get executed?

Â Been proven equivalent to the halting problem.

Â So, each one of these people prove by showing that if you

Â solved it that would be a solution to the halting problem which is undecidable.

Â So, we're going to stamp these undecidable methods.

Â Undecidable problems this way.

Â So, the question is,

Â why are program development environments complicated?

Â They're programs that manipulate programs and

Â therefore they are susceptible to this self-reference idea.

Â But it goes way beyond programming systems.

Â Well, here's another example that's remember

Â Hilbert's Entscheidungsproblem which is the decision problem, is mathematics decidable.

Â Given a first-order logic of

Â mathematical system with a finite number of additional axioms.

Â Is it provable from the axioms using the rules of objects?

Â Or Church had a different formal system called

Â Lambda calculus that he developed in order to try to address this.

Â It's also the basis of modern functional programming languages,

Â that's programming languages based on functions operating on functions.

Â So, if you use Haskell or Java and what Church and Turing

Â showed through equivalence of

Â the lambda calculus and Turing machines in the halting problem is that,

Â Hilbert's Entscheidungsproblem is undecidable.

Â There's many others.

Â The Post's correspondence problem that we gave at the beginning.

Â Can you write a program that takes different kinds of cards is

Â input and tells you whether or

Â not there's an arrangement that has matching top and bottom spring.

Â That was another model of computation and another

Â decade or more later Posts proved that that undecidable.

Â And it's not just Turing problems,

Â computational mathematics is a fine area of

Â important application and nowadays people use systems like

Â a mathematical and sage and MATLAB and other systems.

Â In this that's functions that manipulate functions.

Â So, there's a famous one known as Hilbert's tenth problem,

Â given again around 1900 Hilbert asked,

Â so given the multivariate polynomial,

Â does it have integral roots?

Â That is either integers such that evaluating

Â the polynomial of those integers is equal to zero.

Â So, here's an example,

Â say it's 6X cubed YZ squared plus 3X YZ squared minus X cubed minus 10.

Â Other values of X, Y and Z that make that zero or not.

Â In this case there is,

Â five, three and zero does it.

Â But in this case X squared plus Y squared minus three, there's no way.

Â So, can we have as part of

Â our mathematical manipulation systems facility that you

Â give it a polynomial and it tells you whether or not it has integral roots or not?

Â No, it's undecidable.

Â Well, that was a difficult result that was proved

Â more than 100 years after or around 100 years after Hilbert formulated it.

Â Definite integration, that's something that we'd like to have in

Â our mathematical symbolic manipulation system.

Â So, if you have a rational function that's

Â composed of polynomials and trigonometric functions,

Â you want to know does the definite integral

Â from minus infinity to infinity of that function exist?

Â So, like cosine X over one plus X squared.

Â Yeah, that's pi over here but cosine X over one minus X squared.

Â No. So, if a user types in a rational functional like that,

Â that arises in an application you'd like to,

Â if you can't provide the answer you'd like to at least say that no such thing exists.

Â I can't do it. It's undecidable.

Â From computer science, there's all kinds of different ones.

Â So, data compression.

Â We have a movie, you want to compress it to make it smaller.

Â So, I want to make it as small as I can with the one way to formulate that

Â is given a string find the shortest program that can produce it or given a picture,

Â find the shortest program that can produce it.

Â Remember, we did the Mandelbrot Set.

Â That's a pretty complicated picture reproduced there with a 34-line program,

Â but if some data compression method gets that picture

Â can it figure out a short program to predict it?

Â No, that's undecidable.

Â Virus identification.

Â So, there is a virus out on the web that

Â you load into your computer would be nice to have

Â a program that can analyze the code that you bring into

Â a computer and tell you whether or not it's a virus,

Â it can't, that's undecidable.

Â So, all of those practical applications are extremely important.

Â You should know whether or not the problem's undecidable or not.

Â But really let's review the key ideas in Turing's paper.

Â This is a single paper called

Â Uncomputable Numbers with application to the Entscheidungsproblem.

Â It's been called one of the most impactful scientific papers of the 20th century.

Â In that paper, he introduced the Turing Machine,

Â a formal model of computation.

Â The equivalence of programs and data we encode both programs and their data

Â as strings and we compute with them both the idea of universality.

Â A concept that we can have one device

Â that can compute anything that we know how to compute.

Â The third Church-Turing thesis that says,

Â if you can compute it at all you can computer with the Turing machine."

Â Therefore anything in this universe that computes is equivalent to a Turing machine.

Â The idea that there are limits to

Â computation and there are things that we cannot compute,

Â all of these things were published in this paper in 1936 which is

Â ten years before the earliest computers and we'll talk later

Â about the ENIAC that was worked on in the 40s.

Â All of these things were thought about abstractly before we even had computers.

Â Now, John von Neumann who was a scientist at Princeton,

Â read this paper and talked to Turing and we'll pick up the story later on.

Â But for now, let's talk about the importance of

Â theoretical computer science and Turing's ideas.

Â And he's sometimes called the father of computer science.

Â This is a quote from a famous biography of Turing called,

Â Alan Turing the Enigma written by John Hodges.

Â So he's saying, well,

Â it wasn't only a matter of abstract mathematics,

Â not just a play of symbols,

Â because it involved thinking about what people do in the physical world.

Â It was a play of imagination like that of Einstein or von Neumann,

Â doubting the axioms rather than measuring effects.

Â What he had done was to combine

Â such a naive mechanistic picture of the mind with precise logic of pure mathematics.

Â His machines, which were soon to be called Turing Machines offered a bridge,

Â a connection, between abstract symbols in the physical world.

Â And that's the true significance of this work and it has really

Â had important implications in

Â the development of the computational infrastructure that we now enjoy.

Â Turing showed that the biggest google data center in terms of power,

Â in terms of problems it can solve is no

Â different than the simple model of his universal Turing machine.

Â Quite a stunning result with long lasting implications.

Â