Turing Machines Explained - ComputerphileYouTube↗  IA↗(long shot)
Education  808.9K views 12.5K likes 592 dislikes   29 Aug 2014
Computerphile 2.6M subscribers N/A YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
Back at the start of the 20th century
back at the start of the 20th century
mathematicians were fascinated by the question
mathematicians were fascinated by the
'just how much maths can we do, not by using our
question just how much maths can we do not by using our gut feelings or
gut feelings or intuitions but just by following rules very very carefully
intuitions but just by following rules very very carefully by following an
by following an algorithm'? In order to make that notion precise
algorithm in order to make that notion
we would have to set out: "just what do we mean by a program
precise we would have to set out just what do we mean by a program or
or algorithm" - and this is where Alan Turing came in,
algorithm and this is where Alan Turing
with his notion of a Turing machine.
came in with his notion of a Turing machine cheering was working on a
Turing was working on a problem in Formal Logic
problem in formal logic and as part of
and as part of his proof he had to come up with the notion
his proof he had to come up with a
of any possible algorithm
notion of any possible algorithm or any
or any possible machine. He had to come up with a very general way of capturing
possible machine he had to come up with a very general way of capturing how
how algorithms or programs or machines would work
algorithms or programs or machines would
This is where his notion of a Turing machine comes in. The way Turing
work this is where his notion of a Turing machine comes in the wagering
described these machines goes like this: you have a way of
described these machines goes like this you have a way of writing down
writing down information in a coded form.
information in a coded form his way was
His way was to think of a tape which is as long as it needs to be.
to think of a tape which is as long as
It's divided up into squares and each of the squares there is either one
it needs to be it's divided up into squares and on each of these squares
or a zero or we can have some spaces. Now what our machine does
there's either a 1 or a 0 or we can have some spaces now what our machine does is
is it looks at the tape
it looks at the tape one square at a
one square at a time. So you could imagine it
time so you could imagine it as a little
as a little box running above the tape,
box running above the tape maybe on
maybe on little wheels, looking
little wheels looking one square at a
one square at a time and that information
time and that information codes up a
codes up a question or a problem that we want solved.
question or a problem that we want
What a Turing machine does is really simple
solved what the Turing machine does is
at any moment in time it's in a particular state
really simple at any moment in time it's
and it's looking at one square on the tape, and it has
in a particular state and it's looking at one square on the tape and it has a
a logbook, a program book. And that tells it,
logbook a program book and that tells it
if for instance you're in state number 23
if for instance you're in state number
and you're looking at a zero, then rub out the zero, change it
23 and you're looking at 0 then rub out
to one, move one square to the right,
the 0 change it to a 1 move one square
and move into state number 359,
to the right and move into state number
for instance. Or if you're in state number 359 and you're looking at a one
359 for instance or if you're in State number 359 and you're
leave that one as it is, move one square to the left
looking at a one leave that one as it is move one square to the left and move
and move into state number twenty. Really simple instructions!
into state number 20 really simple instructions what the
what the machine does, is it starts off with a certain
machine does is it starts off with a
pattern of ones and zeros. It
certain pattern of ones and zeros it
follows these rules one square at a time,
follows these rules one square at a time
transforming that string of ones and zeros
transforming that string of 1 and zeros
into a different string of ones and zeros.
into a different string of ones and
And eventually - hopefully -
zeros and eventually hopefully the
the machine moves into a halting state, it is finished, it is done.
machine moves into a halting state it's finished it's done and what's left on
And what's left on the tape is the answer to our problem,
the tape is the answer to our problem
coded up as ones and zeros. That is such a simple
coded up as ones and zeros that is such
process but it turns out it's the
a simple process but it turns out it's
essence of computation. Whatever
the essence of computation whatever any
any computer can do, it could in theory
computer can do it could in theory be
be done by that system looking at ones and zeros
done by that system looking at ones and
on a tape. So that's why we say
zeros on a tape so that's why we say
that Turing in coming up with his idea of Turing machines,
that Turing in coming up with this idea
in effect, came up with a blueprint for modern digital computers.
of Turing machines in effect came up with a blueprint for modern digital
Those computers manipulate strings of ones and zeros
computers those computers manipulate strings of ones and zeros to solve
to solve problems. This really simple
problems this really simple idea that we
idea that we find in Turing machines is actually so
find in during machines is actually so
powerful that all modern computers
powerful that all modern computers
basically do what Turing machines do. And we use this idea
basically do what during machines do and
to evaluate the strength of modern computer programs.
we use this idea to evaluate the strength of modern computer programs
When a computer program can do
when a computer program can do what a
what a Turing machine can do, we call it Turing complete
Turing machine can do we call it
and that is the top of the hierarchy of program strength. So the strongest
cheering complete and that is the top of the hierarchy of program strength so the
program that we can get does exactly what
strongest program that we can get does
a Turing machine can do. We've never come up with a way of computing things
exactly what a cheering machine can do we've never come up with a way of
that could do more than a Turing machine. So
computing things that could do more than
recently, there's been a challenge to the idea
a Turing machine so recently there's been a challenge to the idea that
that anything a computer can do, a Turing machine can do.
anything a computer can do a churring
And the challenge comes from quantum computers which
machine can do and the challenge comes from quantum computers which almost seem like
almost seem like they can do things magically.
they can do things magically my take on
My take on this is that a quantum computer
this is that a quantum computer can't do
can't do more than a Turing machine but it can do things more
more than a Turing machine but it can do
efficiently. For instance, if you asked
things more efficiently for instance if
a classical computer to find you a phone number
you asked a classical computer to find you a phone number in the phone
in the phone directory, you have to look for every single
directory you have to look through every
entry and it takes a long time.
single entry takes a long time but a
But a quantum computer can do that
quantum computer can do that more
more efficiently, don't ask me how. ok
efficiently don't ask me how
look what happens, if I've read a zero, which I have, there.
look what happens if I've read a zero
What do I then do? The answer is I
which I have there what do I then do the
override it with a one. Call that machine H,
answer is I overwrite it with a one call
for the halting problem, if you give me that machine, I could transform it into a
that machine H for the halting problem if you give me that machine I can
different machine,
transform it into a different machine
like this.
like this
Similar videos:

The Turing Test - Computerphile
Computerphile
151.9K views 3.2K likes 22 dislikes 05 Feb 201558% match

Busy Beaver Turing Machines - Computerphile
Computerphile
284.8K views 4.9K likes 52 dislikes 02 Sep 201445% match

Turing & The Halting Problem - Computerphile
Computerphile
684.3K views 11.9K likes 461 dislikes 21 Aug 201444% match

Turing's Enigma Problem (Part 1) - Computerphile
Computerphile
1.1M views 12.6K likes 270 dislikes 28 Nov 201441% match

Parsing Explained - Computerphile
Computerphile
134.2K views 3.6K likes 45 dislikes 13 Nov 201931% match

Fuzzy Logic - Computerphile
Computerphile
335.5K views 5.5K likes 185 dislikes 11 Jun 201431% match

Deep Learning - Computerphile
Computerphile
392.2K views 6.1K likes 280 dislikes 19 Apr 201627% match

PDF, What is it FOR? - Computerphile
Computerphile
409K views 12K likes 144 dislikes 16 Sep 201626% match

Why C is so Influential - Computerphile
Computerphile
1.6M views 22.5K likes 1.6K dislikes 25 Aug 201726% match

Why Use Binary? - Computerphile
Computerphile
588.4K views 10.9K likes 133 dislikes 04 Dec 201526% match

AND OR NOT - Logic Gates Explained - Computerphile
Computerphile
344.7K views 6.8K likes 81 dislikes 06 Mar 201526% match

RFC (Request For Comment) Explained - Computerphile
Computerphile
62.2K views 2.6K likes 44 dislikes 05 Feb 202125% match

Mac or PC? - Computerphile
Computerphile
587.9K views 9.7K likes 314 dislikes 21 May 201425% match

"C" Programming Language: Brian Kernighan - Computerphile
Computerphile
1.5M views 20.4K likes 772 dislikes 18 Aug 201525% match

Lambda Calculus - Computerphile
Computerphile
803.9K views 19.5K likes 567 dislikes 27 Jan 201725% match

How Computer Memory Works - Computerphile
Computerphile
728.7K views 11.6K likes 385 dislikes 23 Jun 201425% match

Internationalis(z)ing Code - Computerphile
Computerphile
911.6K views 32.5K likes 495 dislikes 04 Aug 201424% match

Password Cracking - Computerphile
Computerphile
3M views 60.3K likes 1K dislikes 13 Jul 201624% match

Tail Recursion Explained - Computerphile
Computerphile
104.2K views 5.2K likes 83 dislikes 27 May 202024% match

What is Bootstrapping? - Computerphile
Computerphile
375.1K views 5.5K likes 287 dislikes 19 Mar 201424% match

Where GREP Came From - Computerphile
Computerphile
644.1K views 23.4K likes 152 dislikes 06 Jul 201824% match

ALGOL 60 at 60 - Computerphile
Computerphile
73.7K views 3.1K likes 20 dislikes 04 Jun 202024% match

The Problem with JPEG - Computerphile
Computerphile
412.2K views 6.5K likes 76 dislikes 09 Jun 201524% match

How to Choose a Password - Computerphile
Computerphile
1M views 21.1K likes 235 dislikes 20 Jul 201623% match

Deep Dream (Google) - Computerphile
Computerphile
618.9K views 13K likes 127 dislikes 26 Aug 201623% match

Where HTML beats C? - Computerphile
Computerphile
551.2K views 11K likes 1.3K dislikes 27 May 201622% match

Dijkstra's Algorithm - Computerphile
Computerphile
1.1M views 23.1K likes 392 dislikes 04 Jan 201722% match

Public Key Cryptography - Computerphile
Computerphile
669.9K views 18K likes 224 dislikes 22 Jul 201422% match

How Secure Shell Works (SSH) - Computerphile
Computerphile
741.8K views 16.7K likes -1 dislikes 31 Jan 201922% match

JPEG DCT, Discrete Cosine Transform (JPEG Pt2)- Computerphile
Computerphile
475.3K views 10.4K likes 67 dislikes 22 May 201522% match


Settings Privacy About Contact Donate