Turing Machines Explained - Computerphile
Vložit
- čas přidán 8. 07. 2024
- Turing Machines are the basis of modern computing, but what actually is a Turing Machine? Assistant Professor Mark Jago explains.
Turing & The Halting Problem: • Turing & The Halting P...
Busy Beavers: • Busy Beaver Turing Mac...
Avatars & In-Flight VR: • Avatars & In-Flight VR...
The (pink) VR Simulator: • The (pink) VR Simulato...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
Not even a Turing machine can calculate how oversized that V-neck is
Lol
Facts
Apt
That's what t-shirts look like after a drunken brawl.
🤣 savage you know he saw this n threw that out
Comments section:
1%: nice video
99%: V-neck
Update:
2%: nice video
40%: sneeze speaking
58%: v neck
turing was truly a remarkable genius. he didn't have the life he deserved...
@Yeet Even when he helped to end the war.
@@pysof still mad at that fact tbh
@@pysof yes i read about that, he and fellow cryptographers broke the enigma code of Germany ships
@@AlexandrBorschchev Yupp, there is a movie called "The Imitation Game", its about Enigma and how Turing and his team were able to crack it.
@@AlexandrBorschchev 😔
I like Professor Jago's style when dealing with very high-level computing concepts: he takes it slow, gives us enough time to absorb what he's said, and speaks with as plain a wording as possible. Perfect for this kind of thing.
Where we can find him to benefit from his mind ??
@@khSoraya01 You can find his channel named ‘Attic Philosophy’ on CZcams.
Damn that V-neck tho
hitarophoenix He forgot to wear a turtle neck like you guys... *face palm*
Turtle necks are badass af
GAYLOS
LOL, "A Quantum Computer can do it more efficiently but don't ask me how"
How?
From what I've gathered, by being in two states at once so the answer would be immediately known. It would check and have answered at the same time
@@xavierrenegade846 It can look at all the pages in the directory at the same time like a wave that spreads everywhere at once and once the number is found the wave collapses to that thing that it found.
Watch CS50 (Lecture 0 or 1).
It relies on the thought that the answer is available the second the question is asked. It is both here and there at the same time.
I'm so distracted by how deep his v neck is
they say it has no end
people have died trying to find the bottom
There is no program that can compute if his v-neck will halt or not
There must be a halt!
Get in line!!!!!!!!!
Is it just me or this professor has a built-in real time script writer in his brain. His speech is perfect!
i also noted it
mate he read it off a teleprompter of some kind
Clear thinking can be mathematically formalized.
@@bodenseeboys I actually don't think he did....
brain? :D
I wish my teachers were more like Mark! He puts pauses of the perfect length in the perfect spots such that you have just enough time to absorb what he just said, but not enough time for your mind to wander in the empty space.
He speaks like he's about to sneeze.
+actionmethod It gets annoying after a few times.
+actionmethod do i see a trace of john oliver in this guy?
looks like you just discovered BRITISH ACCENT :D
OMG yes he does.
it's because of the cold from that massive Vneck
lol that little animated Turing machine is so cute.
5:00 How?
I believe it works by using quantum super-positions to check multiple entries at the same time. Once it finds the one it's looking for, it allows the super-position to collapse, leaving you with just the result you were looking for.
That's the gist of it, I believe. I'm not too sure of the details of it though.
It's called Grover's algorithm: en.wikipedia.org/wiki/Grover%27s_algorithm
***** Nope, what you're describing would result in a runtime of O(1) which is impossible with quantum computers.
Umm put it simply, the difference between a nowadays computer and a quantum one is this:
The processors (GPU,CPU) work this way - they get a string of 1 and 0's and they "decrypt" it, by asking wether in a certain position there is a 1 or a 0.
A Quantum Computer wouldn't even have that kind of a process because of a thing called "Super Position" (a state in which a certain object can be in two places at the same time), it would simply remove the asking part since the question was already answered, because it already is in 1 and 0, so no "decryption" is required. Therefore it would be innumerably faster than any computer we have today.
And so it is more efficient just on the basis that it doesn't have to go from 1 to 0 checking which one it is, like a pendulum, it would already be in both of those states.
Borisas ........... what?
Also, the speedup is not "innumerable" but it's very well defined. In this task (searching an unsorted list) it's O(sqrt(n)) instead of O(n).
Amazing crash course on the Alan Turing machine. I just started a new class this week (discrete math). One of the discussion topics asked to describe what a turing machine is and its purpose in the computer science world today. I honestly, watched about 4 other videos on the topic, only to be more confused about its description and functions. Luckily, i'm standing in this legendary checkout line at Burlington coat factory and decided to give this CZcams tutorial another go. I'm nowhere near 100% sure what the machine does and how it works but I get the gist of it now.. Thank you for your explanation.
One abstraction that could be mentioned is that you can have more tape symbols than just "0" and "1" as demonstrated here. Makes it easier to understand a lot of Turing machines because you don't need to have as many states.
Good video. And Brady is a really good cameraman and editor.
Anvilshock What?...
Everyone del there reply lol
Imagine a big company with a lot of employees. At the beginning of the day, the boss prepares the two stacks of cards, either black or white in a lonely cubicle. He then calls over a specific employee to the cubicle, he leaves and waits to be called back. Each employee has a specific job when encountering the two stacks of cards. They check which card is on top of the right stack, and solely based on its color does three things: They replace the top card of the right stack with a card of his own. Then they move (or don't move) the top card of one of the stacks to the other stack. Then they call another specific member of the company over (possibly the boss) and leaves the room. Remember that what the employee does is only based on the card he saw, so each employee has two sets of three instructions. When some employee calls over the boss (as his instruction), the work is finished and the boss checks the result.
In this analogy, the employees form the program, the boss is the user of the computer and the stacks of cards is the input, memory and output of the computer. By giving the employees specific instructions, the boss can have them calculate anything that is (Turing-)computable.
how much does this job pay
That is a description of a Turing machine. It's just unnecessarily complicated.
The employees are the states and the split in the stack marks the position of the read-write head.
r/woosh
I really like the way Professor Mark Jago explains the Turing machine. It really helped me with my essay. Thanks!
The clarity of this video was Turing Complete. Bravo! And thank you
get out.
Illuminati machine
Pastrami machines
I thought Alan Turing was a lizard person, not an Illuminati.
I can't believe nobody got the joke. A symbol of the illuminati is an eye in a pyramid.
Rylan Edlin Well, I got the joke. But I think it's just supposed to be an eye inside a cone. I mean, most speakers and cameras have small working components, even CRT's find their origin ta hte bottom of a cone-like shape, so it's likely not even an intentional one.
Sapphire Crook of course it isn't intentional, that's what makes it funny
I dont know why, but I like this guy and his way to explain things.
onlynamelefthere don't*
I do not care. I am just glad that I can follow the video.
Well put description of computer science as it is. I like this new guy. Not distracted by his attire, I live in NJ and see this at the gym all the time.
But can it run Crysis?
Of course it can. Real world computers are actually less-powerful than Turing Machines. They're one step down the hierarchy. A machine type called a Linear Bounded Automaton. It's basically a Turing Machine, but instead of the tape being infinite, the length is limited with definite endpoints.
Or, to put it another way, if your computer had infinite RAM, it would be a Turing Machine.
you obviously didn't get it.... but thanks
IDidn'tKnowWhatToPutForAChannelNameSoYeah... is a theoretical machine, so it can't
A "real" turing machine, requiring an infinite tape, would take an infinite
amount of time to calculate the algo . This is somehow useless.
So, even a "real" Turing machine would be okay with a finite amount of tape
and take a finite amount of time until the algorithm finishes.
Like modern computer do.
So, actually, modern computers, with a finite amount of RAM, are Turing machines.
@@frankfahrenheit9537 it wouldnt take infinite time. Infinite tape doesnt mean its all used.
I love your way of presenting very complex information!
Without it, I wouldn't be able to explain it to my friends
😋
Anyone also notice the similarity of a animal cell to a turing machine?
"A way of writing information in a coded form" - DNA
Reading the tape - Transcription
Table of instructions - amino acids synthesis.
animal cells are NOT reprogrammable or universally programmable? what's the equivalent of "internal state" in a cell?
"Anyone also notice the SIMILARITY of a animal cell to a turing machine?"
I didn't say that they are identical to a turing machine.
You could also think of mutations as reprogramming DNA ie. radiation or internal changing.
OK. valid.
it's very thought provoking.
@@klam77 But they are. Look what the virus does. It reprograms a cell. The internal state of a cell is the proteins and other elements inside it.
This should have been one of the first videos. Great explanation by the way.
i liked how he speaks slowly
so i can understand clearly, it is maybe boring for you if english is your mother tongue
I needed this video! Good job Mark, thanks.
Epic William Shatner pauses..
SoG Watchman "Epic William Shatner pauses.."
You mean: E --- PIC ---- Will --- IAMSha --- tner --- pau ---- ses, Mr Spock.
I can tell you how a quantum computer is more efficient. The goal of a Turing machine is to transform one configuration to another based on data gathered through observing the original configuration. If the bits (or qubits in the case of quantum though you can use quantum states of any dimension to build a computer ) are highly correlated (entangled) such that measuring one qubit gives you immediate information about another, one can use this information to modify the process with which one completes the transformation. This has the capacity to be more efficient since one gains more information about the system from each observation.
This is very interesting. I've learned a lot more about programming languages through this.
This simple explanation might've just saved me, will update this soon :)
Is it just me or does he double-blink .-.
Milo Szecket >:)
V neck shirts have this effect...
Its an encoded messege
Sharp and concise. It was a fine (short) class, thank you very much Professor Jago!
The way it should be, instead of having to understand the jargon and buzzwords professors love using to make us think it's hard.
@@PiroKUSS more likely to make themselves appear smart, or they don't truly understand what they are talking about.
@@twilight7457 Exactly.
I FINALLY GET IT! Thank you! After reading and watching 5 explanations!
Me too. So, it's a list of bits and a table of states (a program basically made of IF-GOTO statements). The trick is to craft enough states to get you through the entire process.
This is the first time I have properly grasped the fundamentals of a Turing Machine. This probably has a lot do with with the fact that I have recently understood how a CPU works, and a Turing machine is really an abstraction of the function of a modern CPU -- if there even is a meaningful distinction between the two things -- but it is also becasue this is a very clear and concise explanation.
I am glad i found this channel prof ,thanks.
Thanks a lot for making this video! Very simplified!
Can we have an episode on genetic algorithms and/or on neural networks please? That would be a super interesting video.
hello!
Awesome. I enjoyed the simple explanation of turning machine
The noise when the Turing box drops the 1 cracks me up. Like dropping a log into a metal bucket.
Very clear explanation, thank you) Would love to listen one about Lisp Machine
I'm gonna watch this 20 more times so that in 5 days I'll be able to ... kind of.... explain this. Cheers!
that visualisation (1:58) was really helpful, thanks :)
Excellent. Thanks. I've been trying to understand this in Richard Penrose's chapter in his book "The Emperor's New Mind". Trying to understand with very (very) little success. I'm curious as to how much this is due to Penrose's ability to explain to those who ain't so clever and to how much it is to do with the media of instruction. Certainly, I have watched this and am now beginning to understand.
Can the Universe do anything that a Turing machine cannot? There's your next video, Brady!!
Stupendously explained.. Many thanks!!
this was so incredibly helpful!
Awesome explanation.
Two concepts today that I thought were some sort of voodoo magic and come to find I've known these concepts for years in programming. (Lambda Calculus and Turing Machines)
Thank you so much for making this topic approachable.
When written as text, on Wikipedia for example, it was too difficult for this guy to get his head around:)
It is funny when you begin to learn CS or programming, everything looks abstract and incomprehensible, but when you get back to it a time later, it seems so obvious, lol...
Anyway, i still think computer uses magic to work, nobody is going to convince me otherwise... 😝
I love it.
easy to follow video and I get a general understanding of the topic
Finally some useful peice of British education! Been fed up rewinding MIT lectures. Geronimo!
Very nicely explained! Thank you
That is the cutest darn machine I've ever seen.
Bill Cipher would be proud.
One of the best explanations
Churing?
xD
Church-Turing thesis
In England a T with a U after it makes a Ch sound. Diff accents
Chew-ring
from the 46 tunbridge Wells?
can you guys do a video on quantum computing? is that within the field of computer science at most universities, or physics?
It’s been 6 years and quantum computing has made very limited progress since this comment. Right now it’s not looking great for that technology.
Nice simple explanation!
Mark Jago is very good explainer..
This is such a good video. Thank you :).
I loved the "hopefully" thrown out that way at 2:47 :D
This man should be an actor. He is very expressive
Thank you so much that was really helpful!
This is good, thank you! I have seen a working Turing computer in Berlin, but I still struggled to understand it. Even though that should be the most basic thing:)
Very simple explanation!
An episode about quantum computers and how they work would be awesome.
i was wondering what would be a turing complete be. thank you.
great explanation, thanks!
It begs the question, if a turing machine could emulate itself, such that the instruction table was stored on the tape as well as the tape for this simulated machine, how many states would the turing machine need to be able to properly simulate? Would this vary depending on how many states the simulated turing machine has, or the size of the simulated turing machine's alpbabet?
Great video!
"Don't ask me how" really had me cracking up.
That's awesome! Something about Lambda Calculus or maybe even a continuation of the video Programming Paradigms on Functional Porgramming would be veery cool :)
I would love to learn more about quantum computers!
Can Computerphile do a video explaining the concept of quantum computers more in depth? I have heard of them, but do not fully understand the idea. It would be fascinating to learn about them more in-depth.
Not too long ago in late 2018 a couple of PhDs in computer science, published a paper which showed that, relative to an oracle, BQP was not contained in PH.
That is to say that there are problems a quantum computer could solve that would take a classical computer an infinite amount of time.
Doesn't that mean that quantum computers can do things Turing machines simply can't?
A turing machine *can* do that, it would just take a darn long time
@@TowelPanel1852 Fast forward, now doing my masters in computer science and you made me look back at myself and cringe... Thank you ❤️🌹
I was wondering how you could simulate memory without damaging the instruction tape. Would you have to make a new instruction card for each possible state the memory could be in? Because if so, even just a byte of data would require 2^8 cards/states. Is there a way to simplify that?
I don't know what you mean with simulating memory. The Turing machine is essentially a function. You give it an input string and it may give you an output.
I watched it before and feel that i understand it years ago. I watch it again, Now i can comprehend it a little what he's talking about.
Illuminateyyy ! epic video.
Thanks for explaining this.
Thanks for the video!
Man , thanks a lot for explanation ... very nice
could you link to more info about quantum computers doing a lookup that wouldn't require looking up every entry? sounds very interesting
To be fair a normal computer can use tree data structure to look up the desired contact in the phone book which doesn't usually takes time to look up all the pages.
Yes, it's specifically called trie data structure
Wow great explanation :D
Nicely explained
This makes me want to go back to college and study computer engineering again.
Very cool stuff, just have to say, General Zod from Superman 2 called, he wants his shirt back. lol
Thank you so much for ur great talk❤
Thanks for the video.
Not even a Turing machine can calculate this mans speech pattern
super clear. thank you!!!
the phone book example is still blowing my mind
For all wondering why he pauses when he is speaking, count all the times he pauses and you will get a code message.
Hey Computerphile - I wondered, could you tell us something about the game "Arimaa"? I don't know very much about the game itself, but apparently it was created by a computer engineer with the intention of having simple rules, but making it nearly impossible for a computer to play it well.
didnt realise about the tshirt until i read the comments lol. i think it's a fantastic video.
Some episodes about quantum computers would be awesome :)
He made a drastic makeover. I like it.
he was well ahead of his time and to think in a such machine also no one thought about this .
Very clear, thank you
I wanna know how? When you say the computer has to look through every entry, and you say a quantum computer can do it more efficiently? Do you simply mean it can do it faster cause it has more processing power(More states maybe?)...or is there some quantum phenomenon that allows you to search a list with a worst case < n?
This is so interesting Wow Cheers man