Escuro

Turing Complete - Computerphile

Computerphile
Inscrever-se
Visualizações 143 943
98% 3 411 37

What does it mean for something to be Turing Complete? Professor Brailsford explains.
Turing Machine Primer: brvid.net/video/video-DILF8usqp7M.html
Turing Machines Explained: brvid.net/video/video-dNRDvLACg5Q.html
Chomsky Hierarchy: brvid.net/video/video-224plb3bCog.html
What on Earth is Recursion?: brvid.net/video/video-Mv9NEXX1VHc.html
facebook.com/computerphile
twitter.com/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. More at www.bradyharan.com

Publicado em

 

5 Jul 2016

Compartilhar:

Compartilhar:

Baixar vídeos:

Carregando o link.....

Adicionar a:

Minha playlist
Assista mais tarde
Comentários 341
Sapphire Spire
Sapphire Spire Mês atrás
Turing completeness alone is not enough to pass the Turing test. In order to reason like a human, an AI machine must be able, not only to perform math, logic and branching on data but, to orchestrate the process, and to observe and remember the process of orchestration, and improve it.
eatme
eatme 2 meses atrás
ironically, you're using what look like html tags in your graphics as dude mentions all the programming languages that are turing complete -- html is not, if you consider it a language (which it really isnt)
Vadym Dmitrievich
Vadym Dmitrievich 5 meses atrás
Babbage was a great computer scientist. But I think that Turing was the first one, who broke through classical "only mechanical" type of computing machine, and made first (in theory) true cyberphysical computing machine.
qwerty
qwerty 5 meses atrás
Thanks for making
Smrita Pokharel
Smrita Pokharel 5 meses atrás
I just love him.
Zes
Zes 5 meses atrás
wrg
dandelion boy
dandelion boy 7 meses atrás
my microwave is Turing complete. i can input anything and it will return an answer
Sadin Boton
Sadin Boton 8 meses atrás
How about church complete.
haider
haider 9 meses atrás
when he says you must have arbitrary amount of memory (4:50) he runs out of paper to write the whole thing in a straight line. funny.
Existenceisillusion
Existenceisillusion 10 meses atrás
Hello to everyone watching this video now because the lab session was cancelled.
Иля Попов
Иля Попов 11 meses atrás
parallel, series ,inverter.
Crispynugget
Crispynugget Anos atrás
Powerpoint is turing complete Let that sink in
Adrián Domínguez
Adrián Domínguez Anos atrás
This is the ideal male body. You may not like it, but this is what peak performance looks like.
Zes
Zes Anos atrás
no such thing as needx, no worry no matter what. nst as topix or not or so x, argue anyx no mattter what
bred
bred Anos atrás
Brainf**k is probably the simplest Turing complete language
Sirius
Sirius Anos atrás
Damn I just learned a lot.
Jamie Thomas
Jamie Thomas Anos atrás
4:43 Magic occurs & you can hear his pen even when it’s not on the page!
Seeker
Seeker Anos atrás
Came here the first time because of school. Now I'm back because of Ethereum!
SurfingPikachu
SurfingPikachu 2 anos atrás
Powerpoint is also turing complete
Tsavorite Prince
Tsavorite Prince 6 meses atrás
literally everything is turing complete if you try hard enough
Amiy Kumar
Amiy Kumar 8 meses atrás
Brainf**k is also turing complete.
grapes008
grapes008 2 anos atrás
mentions Babbage and forgets Ada Lovelace
--
-- 2 anos atrás
Wow!!! Infinite memory? Why would you need that? If you need infinite memory most likely the outcome is undefined. The process will never end therefore no outcome. I do not think it has meaning in the physical world.
Hunar Omar
Hunar Omar 2 anos atrás
BrainFuck language is turing complete *XD*
Mark Freeman
Mark Freeman 3 anos atrás
Nice vid - thankyou
Aviel Menter
Aviel Menter 3 anos atrás
"The usual suspects: Fortran, Basic, Pascal, Cobol". Professor Brasilford is really showing his age there; it's great.
David Niu
David Niu 5 meses atrás
1:56 "In the late 30's . . ."
Paulo Constantino
Paulo Constantino 3 anos atrás
Am I Turing complete ?
Cannon Fodder
Cannon Fodder 3 anos atrás
How do products such as this get thumbs down?
TheWyrdSmythe
TheWyrdSmythe 3 anos atrás
Dissonance: Watching this video after watching the one where he insists HTML is a programming language.
Guz Man
Guz Man 3 anos atrás
Which language is not Turing complete?
B20C0
B20C0 2 anos atrás
HTML.
CJ Fuller
CJ Fuller 3 anos atrás
Regarding the idea of 'theoretically infinite memory', as soon as you add some kind of external I/O storage device, have you not qualified, as the program and data can be stored and split onto as many extra storage media as you require. It might not be convenient, but it would work...
Heisenberg
Heisenberg 2 anos atrás
The problem still applies. You may have added the capability of increasing memory size, but it's still finite. There is a finite amount of memory in the world (read: on Earth). Let's say that number is n bytes. I can easily define a Turing machine which requires n + 1 memory no matter how large n is. Therefore, there is a theoretical but also practical difference between having finite and infinite memory in a machine; machines with infinite memory can accept languages that machines with finite cannot, as I just showed with my example.
CJ Fuller
CJ Fuller 3 anos atrás
I'm reminded of my own first foray into 'real world' computing as a 16 year old work experience student, at a large government IT department. I wanted to experience computer programming. Instead I was put into a large room housing a huge mainframe and rows and rows of shelves holding sorted and numbered data cartridges. There was a bank of drives, and all day the system would eject cartridges, which had to be re-filed, and start flashing a code for a new cartridge, which I had to retrieve and insert. By the end of the day I was literally reduced to tears, as I was so desperate to see programmers in action, and instead spent the day as a human jukebox disk jockey, trying to keep up with the insatiable demands of this merciless electronic flashing wall of numbers...
wheedler
wheedler 3 anos atrás
I've seen this explained a few times, but this is the first time I think I've actually understood.
Shiny Promises
Shiny Promises 3 anos atrás
so when i complete question N on my tax form, and it says "if no, go to question" N+3, and also has such things as "attach extra pages where required", does this mean my tax form is turing complete?
qwerty687687
qwerty687687 2 anos atrás
It means you are turing complete as you can run the program given by your tax form.
freeman account
freeman account 3 anos atrás
I want to just sit next this guy and listen to whatever he ramble about. I dont take up much space, and I smell nice...
Czesiek
Czesiek 3 anos atrás
please. add the subtitles
Deep Joshi
Deep Joshi 3 anos atrás
Does the smart devices we are using are smart because they are using Turing Complete?
thenewboston
thenewboston 3 anos atrás
Loving these videos, keep it up!
ps4star
ps4star 3 anos atrás
Bukeh!
TheNeweN24
TheNeweN24 3 anos atrás
Buckyyy
Desmaad
Desmaad 3 anos atrás
Would you do a section on esoteric programming languages?
Philipp
Philipp 3 anos atrás
P = NP **flies away**
MrExpresate
MrExpresate 6 meses atrás
That's because that's not even the problem. The variables are not numbers.
wat am i doing?
wat am i doing? Anos atrás
Philipp N=1 I never got why this supposed "unsolvable" problem is even a thing
Felipe Alberto
Felipe Alberto 3 anos atrás
Tosh.0 - Web Redemption - Professor Brailsford programing language
tohopes
tohopes 3 anos atrás
Turing-complete doesn't say anything about I/O. Practical languages don't need infinite memory space, but they do need some form of I/O.
sam loi
sam loi 3 anos atrás
I have done french subtitle for the video, but dont know how it work
David Buchanan
David Buchanan 3 anos atrás
Please do a video on NTRUEncrypt
Aaron Shaver
Aaron Shaver 3 anos atrás
Professor, are you ready to confess that HTML is not a programming language? Confess! Confess!
Untitled
Untitled 3 anos atrás
Sad to see the lambda calculus go unmentioned even though it was discovered before the Turing machine.
Marcin Muszyński
Marcin Muszyński 3 anos atrás
Are humans Turing Machines? Do we have infinite memory to compute?
Owen Prescott
Owen Prescott 3 anos atrás
I'm a designer (noob at programming) currently developing AI for my Unreal Engine video game. I'm familiar with what he's saying from a node(visual) perspective. My question is if I set up a series of events branching off each other to use a loop, does that mean that either my AI systen, the game engine or computer running everything is "turing complete"? In other words, is there a destinction between hardware vs code?
Lydia Spire
Lydia Spire 3 anos atrás
I'm extremely interested in your game now! Keep updates posted somehow.
Conenion
Conenion 3 anos atrás
Game engines have scripting languages that are turing complete. Your computer is running assembler code which is also turing complete. Hardware is "turing complete" (quotes since TC applies only to programming languages, AFAIK), as it is possible to do branching/looping in hardware. Typically you have a state machine in hardware to control the datapath. The datapath does stuff like adding, subtracting, while the state machine decides what is done next. The state is kept in flip flops. The result of an addition or subtraction or whatever is also held in an array of flip flops, which is called a register. I'm at what is called RT level (register transfer), this is just above the gate level (XOR, NAND, AND and so on). What to do in software and what do to in hardware is a decision to be made very early in the design phase. A general purpose computer, like the one in front of you, does not allow much in this regard, as the instruction set of the CPU is fixed. The decision "we'll do this in software in that in hardware" has been made a long time ago.
Camid Daveron
Camid Daveron 3 anos atrás
They were actually talking about turing complete code in this case. The tape head reader/writer is just one way of explaining turing completeness. Here's another way: two computers, P and Q; if P can simulate Q and Q can simulate P then they are *both* turing complete (ignoring that stuff about infinite memory). So, you find turing completeness in all sorts of strange places... most CPU ISAs (what the CPU understands) are turing complete, Assembler language (built on top of a CPU ISA) is turing complete, C, C++, C#, Java, Haskell, Javascript etc. (most well used programming languages) are all turing complete. But then you get other wierd examples of turing completeness: Minecraft (you can make/simulate computers in minecraft). The key point to take away is that turing completeness comes from the system that allows this kind of behaviour (looping + branching). In your example, the AI you've written (although I'm not sure of your exact implementation) is not turing complete; think, "could the AI compute any problem I give it?", "does the AI have the capability of expressing any problem?", I would say _no_ because you've probably made the AI complete a specific set of tasks (pathfinding, offense/defence strategies etc.). To conclude, it is your game engine that is turing complete (and in turn, everything involved in "simulating" that game engine; the language it was written in, your assembler version / CPU ISA).
Xeos Seox
Xeos Seox 3 anos atrás
+Computerphile could you have Professor Brailsford explain if the Ackermann's function would compute with inputs that are complex numbers? Just a question I'm curious about. Thanks for the great videos!
Ashwith Rego
Ashwith Rego 3 anos atrás
I've probably said this before but the animations are extremely helpful in understanding what is being explained!
No-Conspiracy No-Jobs
No-Conspiracy No-Jobs 3 anos atrás
is this abandon shopping cart - complete your order, well I've got infinite loop of 0 - Tuning, casual male, should make things easy
Computerphile
Computerphile 3 anos atrás
+Ashwith Rego thanks! >Sean
trabur metaheap
trabur metaheap 3 anos atrás
2:56 obviously pressing "j" jumps backwards on the tape, pressing "k" toggles it's state, and pressing "l" jumps forwards on the tape. Does that make this video(2:00) {youtube complete}?
trabur metaheap
trabur metaheap 3 anos atrás
goto 6:09 -> "type 1 instead of type 0" -> *keypress 1* -> goto 0:38
trabur metaheap
trabur metaheap 3 anos atrás
program only works when the HTML5 video is selected... hmmm... **keypress = 0** -> "theres 1 thing we keep coming back 2..."
Fendse
Fendse 3 anos atrás
First off, while conditional _branching_ *is sufficient* for turing completeness, it isn't necessary - conditional _execution_ as well as repetition are the necessary and sufficient conditions. Conditional branching just happens to provide both and be useful in everyday computers. But computational classes aren't about modern computer architecture, it's automata and computability. Game of Life is well known to be turing complete, using just a single check repeated over and over - there's nothing analogous to _goto_ or _if_ there. Second, you implied that a computer can recognize arbitrary context-sensitive languages, which is simply not true. In fact, there are even finite languages (a strict subset of the _regular_ languages) which no computer in existence can reasonably recognize (say any language {s, t} where |s| = |t| = 10^5000). As run on any existing computer, no language is even strictly stronger than the regular languages.
Radek
Radek 3 anos atrás
It would be nice if this video discussed the advantages and disadvantages of Turing-complete systems. Right now it's not much more than a recap of Turing machines.
unbreakable footage
unbreakable footage 3 anos atrás
lol the continues change between 50 fps and 30 fps (or is it 24?)
Computerphile
Computerphile 3 anos atrás
25fps - Shot before new camera arrived :) >Sean
Rif Kou
Rif Kou 3 anos atrás
Endless and infinite mean exactly the same thing. So saying "endless, infinite piece of tape" is quite redundant.
David Braude
David Braude 3 anos atrás
The language is Turning complete (C doesn't say you can only use this much memory) but the device it runs on puts on other limitations
Ted Chirvasiu
Ted Chirvasiu 3 anos atrás
Ohh, look! It's that 'HTML is a programming language' guy!
Owen Prescott
Owen Prescott 3 anos atrás
*jumps on him*
Ted Chirvasiu
Ted Chirvasiu 3 anos atrás
Before anyone jumps on me, it was just a joke.
Ian Knight
Ian Knight 3 anos atrás
I was always taught a TM has an 'unbounded' tape, not an infinite tape, whereby your tape is finite length but you can always add another bit to it whenever needed. The point is that at any individual point in time, an unbounded tape will have finite length.
kd1s
kd1s 3 anos atrás
Ah, goto was monster. Gosub or just calling functions in OOP is much better.
Dan Mang
Dan Mang 2 anos atrás
i use return like goto.. returning functions. like.. if this: return this.. else: return that
frognik79
frognik79 3 anos atrás
I don't know where I've heard it but I thought that a part of being turing complete meant that if any one opcode/statement was removed the same result could still be achieved using a conjunction of other opcodes/statements in the same system. I could be thinking of something completely different.
Robert Caldwell
Robert Caldwell 3 anos atrás
Near the end, there was a mistake stated about how memory is finite. The ability for a LANGUAGE to be Turing Complete is the ability for that language to run a TM tape machine, full stop....there is no infinite memory requirement of the statement. On top of that, the software that runs on a computer is not the piece that is being limited by memory, it is the hardware that is limiting....and just as you can increase the length of the TM tape machine towards infinite, you can add bigger HDD space to infinite as well. This means ALL computers possess the ability for type 0 inclusion, the means of which humans put the machines together is what places it into type 1....the languages itself are not at fault of the limitations.
David Yue
David Yue 3 anos atrás
is English Turing Complete? lol I'm so funny eh?
Próximos vídeos
adam and eve talk to god
2:42
Visualizações 977 745
KIDS REACT TO OLD COMPUTERS
7:42
Visualizações 25
Introducing How Computers Work
1:21
Computer Basics: Hardware
28:00
Visualizações 1
BEIJO NA BOCA
2:55
Visualizações 437 489
VINGADORES, A QUEDA: HISTÓRIA COMPLETA
17:56