No video
Turing Machines Explained - Computerphile
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/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...
Пікірлер: 819
Not even a Turing machine can calculate how oversized that V-neck is
@mountfairweather
2 жыл бұрын
Lol
@galatnaamhai5160
2 жыл бұрын
Facts
@Arjun8BPCracker
2 жыл бұрын
Apt
@deanedgx
2 жыл бұрын
That's what t-shirts look like after a drunken brawl.
@ExistentialBordem
2 жыл бұрын
🤣 savage you know he saw this n threw that out
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.
@khSoraya01
3 жыл бұрын
Where we can find him to benefit from his mind ??
@JD-pi2ce
3 жыл бұрын
@@khSoraya01 You can find his channel named ‘Attic Philosophy’ on KZread.
Comments section: 1%: nice video 99%: V-neck
@yegorzakharov8514
3 жыл бұрын
Update: 2%: nice video 40%: sneeze speaking 58%: v neck
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.
Is it just me or this professor has a built-in real time script writer in his brain. His speech is perfect!
@razyazz1
6 жыл бұрын
i also noted it
@bodenseeboys
5 жыл бұрын
mate he read it off a teleprompter of some kind
@dlebensgefahr
5 жыл бұрын
Clear thinking can be mathematically formalized.
@Mogwai88
3 жыл бұрын
@@bodenseeboys I actually don't think he did....
@koja69
2 жыл бұрын
brain? :D
turing was truly a remarkable genius. he didn't have the life he deserved...
@pysof
3 жыл бұрын
@Yeet Even when he helped to end the war.
@DragonRazor9283
3 жыл бұрын
@@pysof still mad at that fact tbh
@AlexandrBorschchev
3 жыл бұрын
@@pysof yes i read about that, he and fellow cryptographers broke the enigma code of Germany ships
@abhishek.rathore
3 жыл бұрын
@@AlexandrBorschchev Yupp, there is a movie called "The Imitation Game", its about Enigma and how Turing and his team were able to crack it.
@_________________404
3 жыл бұрын
@@AlexandrBorschchev 😔
LOL, "A Quantum Computer can do it more efficiently but don't ask me how"
@xavierrenegade846
6 жыл бұрын
How?
@Adultish_Gambino_
4 жыл бұрын
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
@prammar1951
4 жыл бұрын
@@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.
@armstrongtixid6873
4 жыл бұрын
Watch CS50 (Lecture 0 or 1).
@spenserwilliams9167
4 жыл бұрын
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
@asielsmith6007
7 жыл бұрын
they say it has no end
@asielsmith6007
7 жыл бұрын
people have died trying to find the bottom
@Danscottmusic
7 жыл бұрын
There is no program that can compute if his v-neck will halt or not
@joseansalazar8766
7 жыл бұрын
There must be a halt!
@TykoBrian7
6 жыл бұрын
Get in line!!!!!!!!!
Damn that V-neck tho
@gfetco
9 жыл бұрын
hitarophoenix He forgot to wear a turtle neck like you guys... *face palm*
@shawn_2
6 жыл бұрын
Turtle necks are badass af
@nowonmetube
5 жыл бұрын
GAYLOS
5:00 How?
@vukeidge
10 жыл бұрын
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.
@unvergebeneid
10 жыл бұрын
It's called Grover's algorithm: en.wikipedia.org/wiki/Grover%27s_algorithm
@unvergebeneid
10 жыл бұрын
***** Nope, what you're describing would result in a runtime of O(1) which is impossible with quantum computers.
@noosetime9423
10 жыл бұрын
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.
@unvergebeneid
10 жыл бұрын
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).
lol that little animated Turing machine is so cute.
Did anyone appreciate the fact that the video starts with and ends with ? Thanks for explaining this topic
He speaks like he's about to sneeze.
@YawnGod
8 жыл бұрын
+actionmethod It gets annoying after a few times.
@smashinandgrabbin8018
8 жыл бұрын
+actionmethod do i see a trace of john oliver in this guy?
@mehulsharma3044
8 жыл бұрын
looks like you just discovered BRITISH ACCENT :D
@aerialtollhouse7739
7 жыл бұрын
OMG yes he does.
@Lasagnaisprettycool
4 жыл бұрын
it's because of the cold from that massive Vneck
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 KZread 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.
Good video. And Brady is a really good cameraman and editor.
@AV1461
9 жыл бұрын
Anvilshock What?...
@noname_hacke_9747
2 жыл бұрын
Everyone del there reply lol
The clarity of this video was Turing Complete. Bravo! And thank you
@ahmadayazamin3313
4 жыл бұрын
get out.
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.
I really like the way Professor Mark Jago explains the Turing machine. It really helped me with my essay. Thanks!
But can it run Crysis?
@Roxor128
7 жыл бұрын
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.
@benjaminf.3760
7 жыл бұрын
you obviously didn't get it.... but thanks
@gheorghitacristea5750
7 жыл бұрын
IDidn'tKnowWhatToPutForAChannelNameSoYeah... is a theoretical machine, so it can't
@frankfahrenheit9537
6 жыл бұрын
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.
@fgvcosmic6752
5 жыл бұрын
@@frankfahrenheit9537 it wouldnt take infinite time. Infinite tape doesnt mean its all used.
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.
@badmanjones179
8 жыл бұрын
how much does this job pay
@MrCmon113
6 жыл бұрын
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.
@infniitebro8215
6 жыл бұрын
r/woosh
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.
I dont know why, but I like this guy and his way to explain things.
@JorgetePanete
6 жыл бұрын
onlynamelefthere don't*
@jasonbroadway8027
6 жыл бұрын
I do not care. I am just glad that I can follow the video.
i liked how he speaks slowly
Is it just me or does he double-blink .-.
@newcoolvid27
8 жыл бұрын
Milo Szecket >:)
@jacquesm1652
7 жыл бұрын
V neck shirts have this effect...
@oldcowbb
5 жыл бұрын
Its an encoded messege
Illuminati machine
@Chillingworth
10 жыл бұрын
Pastrami machines
@SapphireCrook
10 жыл бұрын
I thought Alan Turing was a lizard person, not an Illuminati.
@RylanEdlin
10 жыл бұрын
I can't believe nobody got the joke. A symbol of the illuminati is an eye in a pyramid.
@SapphireCrook
10 жыл бұрын
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.
@RylanEdlin
10 жыл бұрын
Sapphire Crook of course it isn't intentional, that's what makes it funny
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 FINALLY GET IT! Thank you! After reading and watching 5 explanations!
@bryede
2 жыл бұрын
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.
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.
can you guys do a video on quantum computing? is that within the field of computer science at most universities, or physics?
@bobbythomas6520
Жыл бұрын
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.
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.
@klam77
8 жыл бұрын
animal cells are NOT reprogrammable or universally programmable? what's the equivalent of "internal state" in a cell?
@desmondtheredx
8 жыл бұрын
"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.
@klam77
8 жыл бұрын
OK. valid. it's very thought provoking.
@tasosalexiadis7748
4 жыл бұрын
@@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.
Epic William Shatner pauses..
@mandolinic
9 жыл бұрын
SoG Watchman "Epic William Shatner pauses.." You mean: E --- PIC ---- Will --- IAMSha --- tner --- pau ---- ses, Mr Spock.
Can we have an episode on genetic algorithms and/or on neural networks please? That would be a super interesting video.
@Mogwai88
2 жыл бұрын
hello!
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?
@MrCmon113
6 жыл бұрын
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 love your way of presenting very complex information! Without it, I wouldn't be able to explain it to my friends 😋
That is the cutest darn machine I've ever seen. Bill Cipher would be proud.
Sharp and concise. It was a fine (short) class, thank you very much Professor Jago!
@PiroKUSS
Жыл бұрын
The way it should be, instead of having to understand the jargon and buzzwords professors love using to make us think it's hard.
@twilight7457
Жыл бұрын
@@PiroKUSS more likely to make themselves appear smart, or they don't truly understand what they are talking about.
@PiroKUSS
Жыл бұрын
@@twilight7457 Exactly.
This simple explanation might've just saved me, will update this soon :)
Finally some useful peice of British education! Been fed up rewinding MIT lectures. Geronimo!
Can the Universe do anything that a Turing machine cannot? There's your next video, Brady!!
For all wondering why he pauses when he is speaking, count all the times he pauses and you will get a code message.
that visualisation (1:58) was really helpful, thanks :)
I'm gonna watch this 20 more times so that in 5 days I'll be able to ... kind of.... explain this. Cheers!
The noise when the Turing box drops the 1 cracks me up. Like dropping a log into a metal bucket.
Churing?
@justjcs
8 жыл бұрын
xD
@theguythatcoment
7 жыл бұрын
Church-Turing thesis
@fromthe4621
6 жыл бұрын
In England a T with a U after it makes a Ch sound. Diff accents
@ch3ragCS
5 жыл бұрын
Chew-ring
@chrispettinga
5 жыл бұрын
from the 46 tunbridge Wells?
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?
@TowelPanel1852
2 жыл бұрын
A turing machine *can* do that, it would just take a darn long time
@factsheet4930
2 жыл бұрын
@@TowelPanel1852 Fast forward, now doing my masters in computer science and you made me look back at myself and cringe... Thank you ❤️🌹
Not even a Turing machine can calculate this mans speech pattern
This should have been one of the first videos. Great explanation by the way.
How many A-level students we got here...
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:)
@sophiacristina
Жыл бұрын
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... 😝
Very cool stuff, just have to say, General Zod from Superman 2 called, he wants his shirt back. lol
I needed this video! Good job Mark, thanks.
2:55 What is left on the tape is the answer to our problem 1:42 Each box codes up a question or problem that we want solved Is each box a seperate problem or/and question or is the whole tape one question/problem?
One of the best explanations
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?
turing was such a genius and a true pioneer of the v neck
didnt realise about the tshirt until i read the comments lol. i think it's a fantastic video.
I am glad i found this channel prof ,thanks.
Will you do a video on quantum computers?
@gheorghitacristea5750
7 жыл бұрын
randomviewer896 he said at 5:01that he doesn't know how quantum computer work😂
@nowonmetube
5 жыл бұрын
@@gheorghitacristea5750 you know that Computerphile isn't just run by this one guy, right?
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.
Mark Jago is very good explainer..
Very simple explanation!
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.
@aaravgulati2
Жыл бұрын
Yes, it's specifically called trie data structure
I love it. easy to follow video and I get a general understanding of the topic
The phone number is alphabetically sorted, you don't have to look at any entry. Just do a binary search ;) But it is a great video nevertheless! The simplest explanation of a Turing machine I heard so far!
@Kalumbatsch
9 жыл бұрын
MrNightLifeLover If you are looking for a name, that's true. But he was talking about looking for a number. Usually, phone books are not sorted by number.
There can be spaces (empty bits) in the tape? Does that mean that each spot (bit) has 3 possible values in a Turing machine whereas normal computers can only hold 1 or 0 in each memory spot?
What causes a halting state? How is what is left the answer? I don't get how this decrypts anything? I know you are talking about how the machine works in general, but tying that to successful decryption would help a lot in understanding.
Awesome. I enjoyed the simple explanation of turning machine
What do you mean when you say a program is turing complete? I always thought it was the computer that replicated the turing machine, or even the programming language. If programs are algorithms does this mean any algorithm that reads, writes, conditional branches and loops is turing complete?
Awesome explanation.
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?
I am not sure that the term “Turing completeness” could be applied to programs, as you say at 3'50". I had heard this notion in regard to computer programming languages, or set of rules (as Conway's Game of Life).
i was wondering what would be a turing complete be. thank you.
Is it understood correctly, if we think of eye as the processor and the tape as the memory as per the modern computer architecture.
This man should be an actor. He is very expressive
What happens if the "if" is not satisfied? For example, if in say State 100: if 1 then etc etc. But it's in a 0, so what's it going to do next? Or that never happens?
Thanks for explaining this.
What do you mean by "state"? Ex. do you mean "square" number 23 when you say "state" number 23?
@raykent3211
8 жыл бұрын
I'm a bit late, but it seems nobody else has answered your question, so here goes. What do you need to do to change up a gear in a car? Well, that depends on what gear you're already in. This "what gear you're already in" can be called the current "state" of the gearbox. If you see you're currently in state 3 (third gear) you move the stick in a particular way and "enter state 4". To change up from there you need to move the stick differently. The little cards shown in the video tell the machine how to move the gearstick according to the position, or state, that it's currently in. In effect, they are the computer program.
Pure genius.
Is there anything like Computerfile but for Law?
Nice simple explanation!
could you link to more info about quantum computers doing a lookup that wouldn't require looking up every entry? sounds very interesting
Thank You Today I've learned how the most interesting theory works.
The Touring machine was Alan's curse and blessing to the world.
An episode about quantum computers and how they work would be awesome.
This is very interesting. I've learned a lot more about programming languages through this.
Stupendously explained.. Many thanks!!
Nicely explained
I see that this kind explanation may lead to the misleading question: >. Since he uses the term "logbook", I would rather express it as: "if ... move left and go to the logbook entry N", so it becomes clear that there is an unwritable memory (the "logbook") --- which is the program -- and another writable memory (the "tape") -- which is used both for "program input", "storage of program variables" and "program output" in programming terms.
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.
I had no idea how turing machine works before watching this video. After watching this video and thinking for a while I realized I am 6 minutes older.
Very clear explanation, thank you) Would love to listen one about Lisp Machine
Great video!
so is there a search for an alternate algorithm for computation? Or a proof of impossibility of such a thing? Or is that not something people are interested about with quantum computers coming up?
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.
I would love to learn more about quantum computers!
Thanks a lot for making this video! Very simplified!
I loved the "hopefully" thrown out that way at 2:47 :D
"Turing Machines Explained" You have barely even scratched the surface
Great video, however I feel like the explanation of the State Machine control program might have been a little unclear for a non-computer scientist.
thanku ........... plz make more video on what deterministic, non-deterministic means what is context free grammer ...... what is mean by deciadibility and non-deciadibilty ?????