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.
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.
I know this is a 10 year old video but I just want to say that was one of the best explanation and descriptions of a Turing machine and how it works I've heard! It's such a seemingly "simple" concept, at least once you understand it, but it can SO incredibly hard to properly explain to someone without either oversimplify things a bit too much and leaving a lot unexplained, or the exact opposite, and ending up having the explanation being too in-depth & complex and leaving the person more confused and with more questions than before you tried to explain it. I'm definitely going to be pointing people to this video when they want a super quick and easy to understand explanation of what Turing Machine is.
@@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.
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 TH-cam 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.
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.
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).
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 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 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.
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.
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.
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.
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.
"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.
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.
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.
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.
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!
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.
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.
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?
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 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 prosecuted for homosexuality in 1952, when such acts were still criminalised in the UK. He accepted treatment with oestrogen injections (chemical castration) as an alternative to prison. Turing died in 1954, 16 days before his 42nd birthday, from cyanide poisoning. An inquest determined his death a suicide.
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?
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.
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?
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.
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?
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.
Because of the band the turing machine can memorize things and therefore is more powerful. A finite state machine can decide only regular languages. Try to define a meally machine that decides the language of all word of the form 0^n1^n for every natural number n (like 0011, 000111, 000000111111). You can't.
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?
it feels like you're leaving out important parts, that bind facts together. E.g. the theory is nice, but why is it necessary? What advantage gives us? We could build computers without that idea / machine.
I think the video was somewhat misleading. Turing machines aren't really relevant to technology, but rather to theoretical considerations. A Turing machine is a very simple way to describe a very powerful system, but there are much better ways to implement most (interesting) functionalities in practise.
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.
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?
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?
If I understand it correctly, while a regular computer calculates a binary state of 1 and 0, a quantum computer calculates states of 1, 0, both, and neither simultaneously. I assume this to mean it would read every page in the phone book at the same time while writing a list of every possible combination of numbers for a phone number and marking off each one that shows up with a name and page number for reference.
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.
SO to solve a problem with a turing machine, one must first transform the problem into a generalized set of instructions for each state? How does this compare to the way modern programming languages use classes and methods?
Those programs are translated into assembler code, which is itself Turing complete. I think it is closely related to GOTO statements, which are also just as powerful as Turing machines.
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).
thanku ........... plz make more video on what deterministic, non-deterministic means what is context free grammer ...... what is mean by deciadibility and non-deciadibilty ?????
I've heard of classifications of computers as finite-state automata that should similar to this... Is an automata actually similar or the same as a Turing machine?
TheAl_T The OP was commenting on the fact he said "a computer needs to traverse through all the phone numbers". The hash table is a data structure where it does not.
BinaryHistory That's nice, but that wasn't the point. He is talking about looking for a number in a phone book (an unsorted database). The point is that Grover's search algorithm on a quantum computer can find the number asymptotically (quadratic speedup) faster than a classical (non-quantum) computer.
BinaryHistory And how will you create that hash table? You will have to read the phone book at least once and flag the relevant hash entries. What the gentleman in the video said about quantum computers is true. If you have a function that tells what phone number is in what page and what position in the phone book, a quantum computer can tell you where the desired phone number is in that phone book without ever traversing it fully. Ever. That can NOT be done using ANY classical computer, and looks like magic, but its not.
At 2:05, shouldn't we also have a rule that tells the machine what it would do if it reads a '1'? We know what to do in the '0' case, but not the other case. There should be a rule for each state the machine could be in, and also for each symbol the machine could read while in that state, no? If I'm understanding correctly, that is
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 TH-cam.
Right 👍
Did anyone appreciate the fact that the video starts with and ends with ? Thanks for explaining this topic
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
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
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.
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 😔
Comments section:
1%: nice video
99%: V-neck
Update:
2%: nice video
40%: sneeze speaking
58%: v neck
I know this is a 10 year old video but I just want to say that was one of the best explanation and descriptions of a Turing machine and how it works I've heard!
It's such a seemingly "simple" concept, at least once you understand it, but it can SO incredibly hard to properly explain to someone without either oversimplify things a bit too much and leaving a lot unexplained, or the exact opposite, and ending up having the explanation being too in-depth & complex and leaving the person more confused and with more questions than before you tried to explain it.
I'm definitely going to be pointing people to this video when they want a super quick and easy to understand explanation of what Turing Machine is.
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.
The clarity of this video was Turing Complete. Bravo! And thank you
get out.
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!!!!!!!!!
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 TH-cam 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.
Anvilshock What?...
Everyone del there reply lol
lol that little animated Turing machine is so cute.
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.
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).
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.
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
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 really like the way Professor Mark Jago explains the Turing machine. It really helped me with my essay. Thanks!
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 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.
Finally some useful peice of British education! Been fed up rewinding MIT lectures. Geronimo!
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.
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
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.
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.
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.
This simple explanation might've just saved me, will update this soon :)
I love your way of presenting very complex information!
Without it, I wouldn't be able to explain it to my friends
😋
i liked how he speaks slowly
This should have been one of the first videos. Great explanation by the way.
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
Is it just me or does he double-blink .-.
Milo Szecket >:)
V neck shirts have this effect...
Its an encoded messege
Can we have an episode on genetic algorithms and/or on neural networks please? That would be a super interesting video.
hello!
I am glad i found this channel prof ,thanks.
that visualisation (1:58) was really helpful, thanks :)
I needed this video! Good job Mark, thanks.
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!
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.
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'm gonna watch this 20 more times so that in 5 days I'll be able to ... kind of.... explain this. Cheers!
That is the cutest darn machine I've ever seen.
Bill Cipher would be proud.
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?
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.
Can't believe this video is 10 years old yet feels like fresh out of oven
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... 😝
The noise when the Turing box drops the 1 cracks me up. Like dropping a log into a metal bucket.
For all wondering why he pauses when he is speaking, count all the times he pauses and you will get a code message.
One of the best explanations
This man should be an actor. He is very expressive
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 prosecuted for homosexuality in 1952, when such acts were still criminalised in the UK. He accepted treatment with oestrogen injections (chemical castration) as an alternative to prison. Turing died in 1954, 16 days before his 42nd birthday, from cyanide poisoning. An inquest determined his death a suicide.
Epic William Shatner pauses..
SoG Watchman "Epic William Shatner pauses.."
You mean: E --- PIC ---- Will --- IAMSha --- tner --- pau ---- ses, Mr Spock.
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 ❤️🌹
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.
Mark Jago is very good explainer..
Can the Universe do anything that a Turing machine cannot? There's your next video, Brady!!
This is very interesting. I've learned a lot more about programming languages through this.
Awesome. I enjoyed the simple explanation of turning machine
turing was such a genius and a true pioneer of the v neck
how did he programed the sensor to move?
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?
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.
Is it understood correctly, if we think of eye as the processor and the tape as the memory as per the modern computer architecture.
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?
Straight to the point. Thank you.
Is there anything like Computerfile but for Law?
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.
What do you mean by "state"? Ex. do you mean "square" number 23 when you say "state" number 23?
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.
Will you do a video on quantum computers?
randomviewer896 he said at 5:01that he doesn't know how quantum computer work😂
@@gheorghitacristea5750 you know that Computerphile isn't just run by this one guy, right?
I love it.
easy to follow video and I get a general understanding of the topic
If Alan had my name and used the same naming convention, it'd be the Mulligan Machine. Sounds ridiculous!
wait when I studied about meally machines last semester the description was pretty much the same so what is the deffirence between the two?
Because of the band the turing machine can memorize things and therefore is more powerful. A finite state machine can decide only regular languages. Try to define a meally machine that decides the language of all word of the form 0^n1^n for every natural number n (like 0011, 000111, 000000111111). You can't.
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?
Is assembly language what tells the reader to do?
Awesome explanation.
Stupendously explained.. Many thanks!!
it feels like you're leaving out important parts, that bind facts together. E.g. the theory is nice, but why is it necessary? What advantage gives us? We could build computers without that idea / machine.
I think the video was somewhat misleading. Turing machines aren't really relevant to technology, but rather to theoretical considerations. A Turing machine is a very simple way to describe a very powerful system, but there are much better ways to implement most (interesting) functionalities in practise.
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
yes but can it run crisis?
Nice simple explanation!
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?
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?
If I understand it correctly, while a regular computer calculates a binary state of 1 and 0, a quantum computer calculates states of 1, 0, both, and neither simultaneously.
I assume this to mean it would read every page in the phone book at the same time while writing a list of every possible combination of numbers for a phone number and marking off each one that shows up with a name and page number for reference.
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.
Thanks a lot for making this video! Very simplified!
SO to solve a problem with a turing machine, one must first transform the problem into a generalized set of instructions for each state? How does this compare to the way modern programming languages use classes and methods?
Those programs are translated into assembler code, which is itself Turing complete. I think it is closely related to GOTO statements, which are also just as powerful as Turing machines.
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.
What do you mean by states here?
Is this the same Turing as in the Turing test? For AI
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).
thanku ........... plz make more video on what deterministic, non-deterministic means what is context free grammer ...... what is mean by deciadibility and non-deciadibilty ?????
is there a souce for what he says?
I've heard of classifications of computers as finite-state automata that should similar to this... Is an automata actually similar or the same as a Turing machine?
A Turing machine is a kind of automaton.
4:45 Let's just throw away all advancements in sorting algorithms.
Nicholas Pipitone I think he is talking about unsorted phonebook
In hash table the time needed to lookup a phone number is basicaly O(1). I dont think he ment that.
TheAl_T The OP was commenting on the fact he said "a computer needs to traverse through all the phone numbers". The hash table is a data structure where it does not.
BinaryHistory That's nice, but that wasn't the point. He is talking about looking for a number in a phone book (an unsorted database). The point is that Grover's search algorithm on a quantum computer can find the number asymptotically (quadratic speedup) faster than a classical (non-quantum) computer.
BinaryHistory And how will you create that hash table? You will have to read the phone book at least once and flag the relevant hash entries. What the gentleman in the video said about quantum computers is true. If you have a function that tells what phone number is in what page and what position in the phone book, a quantum computer can tell you where the desired phone number is in that phone book without ever traversing it fully. Ever. That can NOT be done using ANY classical computer, and looks like magic, but its not.
At 2:05, shouldn't we also have a rule that tells the machine what it would do if it reads a '1'? We know what to do in the '0' case, but not the other case. There should be a rule for each state the machine could be in, and also for each symbol the machine could read while in that state, no? If I'm understanding correctly, that is
Not even a Turing machine can calculate this mans speech pattern