Turing Machine Primer - Computerphile
155,614
Published 2014-09-04
Professor Brailsford's code and further reading: bit.ly/busybeaver
Turing and the Halting Problem: • Turing & The Halting Problem - Comput...
Busy Beaver Turing Machines: • Busy Beaver Turing Machines - Compute...
Domino Addition – Numberphile: • Domino Addition - Numberphile
Ackermann Follow Up: • Ackermann Follow Up - Computerphile
'Turing Machines Collection' Playlist: • Turing Machines Collection - Computer...
“The Most Difficult Program to Compute?” (Original Ackermann Film): • The Most Difficult Program to Compute...
www.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. See the full list of Brady's video projects at: bit.ly/bradychannels
All Comments (21)
-
I like his voice, it's at that right soft, listenable sound
-
Thanks for this. Sometimes a step-by-step leading by the hand explanation is necessary for people like myself, and it is quite appreciated. I really love these nuts and bolts views under the hood of computing and I feel enriched watching the videos presented by an encouraging and wonderful instructor; it's absolutely fascinating that people have invented this stuff. People are awesome when they put their minds to things... I sure wish I'd been privileged enough to attend class taught by any of the instructors on these channels :0) Thanks Sean and all!
-
More videos Professor! It's really good to hear you explaining!
-
I almost didn't understand the Busy Beaver before this video was posted, now I don't understand why this video wasn't posted before Busy Beaver.
-
The professor is a legend
-
This was an excellent explanation, well done.
-
THANK YOU!
-
Oh my God. The instruction card finally clicked for me. That took me FOREVER to understand!
-
I think it makes sense to have the head of the Turing machine move at every step. If some Turing machine does not move on a given step, it can be combined with the next step because the next step will read the datum written on this step.
-
What if you have multiple heads reading and writing in that same (sending information or not between) time on multiple tapes.
-
Your video is wonderful! Thank you very much
-
My question is, what does it mean for a Turing Machine to have each register of the tape have an infinite amount of symbols instead of just a one and a zero? (To prevent the risk this thought experiment going into a higher computational complexity, I will say that the number of characters is a countable infinity.) Does this provide the ideal situation for a given program with the minimal number of registers as possible? (And I for one are for being self-destructive when it comes to Turing Machines, and allowing them to "rewrite" zeroes into zeroes or ones into ones. Because why not? It is so much better that way. And by better, I mean, makes things more complicated.)
-
You know, I would almost prefer a turing machine which doesn't follow Tibor Rado's method; one which instead keeps the program code on the tape like the Von Neumann architecture. This would allow the turing machine to be a universal turing machine and it just seems like a more pure model.
-
1:41 yes I'm completely masochistic xD
-
Why is this video unlisted?
-
Really great something that i inconsciously already know but without definiying all these therms.I was like wtf his just explain how cpu bit works then i realised aww that what we call a TM ^^
-
Binary Turing Machines just remind me of languages like Brainf*ck. Wonder if that's where they got inspiration.
-
This could be really simple to program myself, using arrays.
-
Interesting. Have watched all videos so far and yet little mention to how an upgraded version of a Turin machine makes a computer (because it is :) ). The way this topic is put in this video series, makes obvious how fundamental this construction is. That's why, I like the video 'Turing & The Halting Problem' because it explores the limits of this type of machine, and any other type actually.
-
yiis machin praimerr