Turing Complete - Computerphile

What does it mean for something to be Turing Complete? Professor Brailsford explains.
Turing Machine Primer: • Turing Machine Primer ...
Turing Machines Explained: • Turing Machines Explai...
Chomsky Hierarchy: • Chomsky Hierarchy - Co...
What on Earth is Recursion?: • What on Earth is Recur...
/ 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. More at www.bradyharan.com

[@AvielMenter]

"The usual suspects: Fortran, Basic, Pascal, Cobol". Professor Brasilford is really showing his age there; it's great.

[@davidniu6843]

1:56 "In the late 30's . . ."

[@Okkarator]

If you study for example meteorology nowadays at some universities you still learn Fortran (90/95) because the weather and climate simulation models are written in that language 😉 I‘m 30 and learned Fortran four years ago! 😅

[@WilliamFord972]

@@Okkarator I hear it’s a real problem: there are so few people who know Fortran that industries that use it can’t find employees.

[@robertbruce7686]

And your point being?

[@web2dataweb2data14]

@@WilliamFord972 What industries do you mean?

[@jeremiahglover7562]

"You must have an arbitrary amount of memory" he says as he runs out of paper.

[@ashwith]

I've probably said this before but the animations are extremely helpful in understanding what is being explained!

[@Computerphile]

+Ashwith Rego thanks! >Sean

[@currentphonograph1734]

is this abandon shopping cart - complete your order, well I've got infinite loop of 0 - Tuning, casual male, should make things easy

[@freemanaccount5146]

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...

[@kristiyanivanov7414]

freeman account same

[@thenewboston]

Loving these videos, keep it up!

[@Computerphile]

+thenewboston thanks! >Sean

[@TheNeweN24]

Buckyyy

[@SeanKD_Photos]

I'm building a computer in Minecraft using Redstone and these videos help a lot :)

[@Omeomeom]

like an actual computer?

[@pleasedontwatchthese9593]

Yeah from the subatomic level

[@SeanKD_Photos]

+Kappa Kapplin 8 bits, but yeah an actual computer with memory and conditonal branching

[@peppybocan]

build a Java VM inside a Java VM and run an Ackermann function on it.

[@bace1000]

I just drew a 4-bit computer for my own logic simulator. Message me if you need some help :)

[@pusheenomics]

This is the ideal male body. You may not like it, but this is what peak performance looks like.

[@Thymesicle]

if it's Turing complete it can run Doom

[@andrewpinedo1883]

As long as they have graphics controls, yes.

[@NickCybert]

5:25 That's look of a teacher who's is relieved to see his student finally learning something after how many Professor Brailsford videos has it been now? Nice work Sean.

[@PJoelJ]

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.

[@Rust_Rust_Rust]

No

[@datenegassie]

Yay! Illuminati-bot is back!

[@pbpbpbpbpbpbpbpbpb]

Yaaaaayyy Illuminati!

[@ChadieRahimian]

=)))))

[@metacustomcomputers3426]

GOTO, or "How to spaghettify your code". :) Kind regards, Meta Custom Computers

[@dddtl]

It's also hugely useful as a fatal exception handler.

[@fbafelipe7666]

It's also hugely useful to cause the fatal exceptions with bugs on the spaghetti code

[@mattcay]

Well, in anything higher-level than assembly that is true. When you get right down to the metal however, goto's are absolutely necessary -- that's how you implement branching, that's how you implement loops and a lot of other things that are abstracted away by a higher-level language like C, C++ or pretty much every programming language in the world.

[@metacustomcomputers3426]

In machine-code the GOTO is fundamental, that's why I thought it's trivial that my joke was targeted at high-level-languages. My teachers hammered it into our heads like a dogma: "GOTO is bad style!". Kind regards, Meta Custom Computers

[@alexparker7791]

Knuth said that Dr. Goto cheerfully complained that he was always being eliminated :)

[@dp0om88mo0qb]

I love truly enthusiastic teachers, they make everything so much more interesting.

[@realshaoran4514]

Nice video. But when Professor Brailsford mentioned Charles Babbage, I hoped he mentioned Lady Ada Lovelace as well, but he didn't :(

[@subvind]

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}?

[@DasAntiNaziBroetchen]

No. Where's the branching?

[@vadymdmitrievich843]

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.

[@xamidi]

@Seth Bradford Wagenman No. Creating mathematical objects in theory. You have to define them to talk about them, they're abstract objects. Not merely mental objects, but also not physical ones.

[@TheRojo387]

It's cool beyond belief. A machine need not actually produce sound OR graphics to be Turing-complete; just represent them through math!

[@conkerconk3]

Literally got emotional for some reason, as soon as i saw Conway's game of life being played on Conway's game of life, using something called an OTCA Metapixel...

[@derstreber2]

What?? No mention of HTML at all?? Well there is nothing for me to argue about this time.

[@BGroothedde]

"HTML is not a programming language, it is more like C++" - Are you triggered now?

[@danriddick914]

Is HTML turing complete though? Might just be semantics... I'd agree that I'd think HTML/CSS is turing complete, but it requires both parts to me.

[@Bitflip32]

"So what are the skills that you're going to bring to this job?" "Well, I know the HTML programming language very well!" "...get out."

[@ender_scythe2879]

Hey, Bas, what are those pluses for? The only real programming language is Assembly/Assembler.

[@BGroothedde]

+ender_scythe haha

[@haider4899]

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.

[@robchr]

Unfortunately he only explains what a Turing machine is without saying what it means to be Turing complete. At the root of the problem when we say something is Turing complete we are saying computationally universal. Meaning it can calculate anything that is calculable. This distances it from the very abstract yet mechanical Turing machine. Like he said we could call it Babbage complete, or Church complete, or Java complete etc. I personally find Lambda Calculus which was defined before the Turing machine more useful for writing programs to than a Turing machine. But both are equal in a computability sense.

[@jeffirwin7862]

Upvote because Fortran was the first language named.

[@InkDevil999]

For those interested in how computers work there is a game called Turning Complete where you learn about different gates, registers, bits/bytes, busses and others. It is possible to make a whole computer in the game from the ground up. I know some people have build Intel CPUs or Tetris and Snake on a computer they themselves have built.

[@datboi1861]

Is it free to play?

[@InkDevil999]

@@datboi1861 no it's not but it is very much worth it imo.

[@InkDevil999]

@@datboi1861 just checked on Google and it should be 19.99$

[@datboi1861]

@@InkDevil999 Alright. Thanks. I'll check it out.

[@Hunar1997]

BrainFuck language is turing complete *XD*

[@TheWyrdSmythe]

Dissonance: Watching this video after watching the one where he insists HTML is a programming language.

[@meepisdispenser5651]

html is turing complete given very simple js events which is kinda cheating but oh well also turing completeness isnt a necessity for coding langs.

[@thedoublehelix5661]

@@meepisdispenser5651 js is cheating, but html + css is indeed turing complete

[@want-diversecontent3887]

You can make a quine in HTML+CSS so it's fine with me

[@pev_]

If you include the demand for infinite memory into turing completeness then turing completeness means nothing. NOTHING in real life is ever infinite.

[@ianknight5120]

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.

[@monavie9110]

neat

[@Tendomcgoobin]

I'll be danged

[@KarjamP]

Video's incomplete in its description on what constitutes a Turing Completeness: a Turing complete system must be able to simulate the tape head in some way. Without this requirement, things such as the "Buzy Beaver" problem would be impossible within the systems. Thankfully, most programming languages are able to do this. Just use arrays or pointer arithmetic to simulate this.

[@randomdogdog]

i thought that Turing machine simulation was a result of being Turing complete

[@boptillyouflop]

That's what "arbitrary amount of memory" means... it implies the tape head, because without the tape head, your amount of usable memory is only finite.

[@sundhaug92]

You don't really need actual arrays though, you can use a0, a1, a2... to emulate the functionality of a constant-sized array a

[@boptillyouflop]

sundhaug92 Ah, but for Turing-completeness, constant-sized arrays don't cut it, you need variable-sized data structures.

[@KarjamP]

+boptillyouflop "Arbituary amount of memory" doesn't by itself imply this requirement. It's possible to have an arbituary amount of data without the ability to group variables together in a way that resembles array data structures (which is essentially what the tape is). An example I can think of would be a pure stack-based system that allows you to push and pop variables, but not the ability to reference variables from earlier in the stack. Such systems are no better than the simple calculator in this regard.

[@Jaice00]

Powerpoint is also turing complete

[@alice_in_wonderland42]

Brainf**k is also turing complete.

[@miljoneir]

This video was suggested to me after watching that "Powerpoint is turing complete" clip.

[@EE-wp9qr]

@@alice_in_wonderland42 technically vanilla BF has a limited array of bytes remove that and it would be tho

[@VeganCheeseburger]

Professor, are you ready to confess that HTML is not a programming language? Confess! Confess!

[@PvblivsAelivs]

Strictly speaking, of course, every computer we have is a finite-state machine. They go from one state to the next by means of electrical signals (including clock pulses) coming in. Computers are not normally _thought of_ as finite-state machines largely because it would be impractical to try to draw a state diagram. (There are more possible states than there are atoms in the known universe. But it is still a finite number.)

[@xeosseox4542]

+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!

[@foldr431]

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.

[@mightyNosewings]

". . . you can show that just the ability to write on a tape patterns of 0s and 1s is powerful enough to compute anything that can be computed." Strictly speaking, this isn't true. The Church-Turing thesis isn't a theorem -- it's not even a mathematical conjecture -- it's an assertion. It's not the kind of thing that can be expressed formally, so it can't be proven. Of course, we have good reason to believe it, since we've found lots of Turing-equivalent systems and no super-Turing systems, but it remains theoretically possible that super-Turing systems do exist.

[@pancakerizer]

If there are a finite number of particles in the universe, wouldn't that mean that a Turing complete machine is impossible?

[@xanthirudha]

'If our brains were simple enough for us to understand them, we'd be so simple that we couldn't.'Ian Stewart -

[@Conenion]

Chuck Norris built a turing machine despite finite number of particles in the universe. Twice.

[@dekippiesip]

Definitely.

[@derfettegarfield]

I don't think it actually matters that we only have finite hardware. What is described is a property of a programming language. So the question is not "Can we with our resources build it to be an exact TM?". But rather: "Does the language behave like the software of a TM?". So in the example of finite hardware the requirement to the language should in my opinion just be: "Could it handle an infinite hardware and still meet the other TM requirements?"

[@oafkad]

Babbage is one of my favorite names. So great.

[@xoio]

Given this video is about stating explicitly WHAT is required to be Turing Complete (TC). Therefore is it to be assumed that 'Indirect Addressing' is NOT a requirement to be TC after-all. Because if it were, it would be mentioned surely?

[@peteranderson037]

I strongly disagree with the assertion that if a computer does not have an infinite amount of memory then it is not Turing complete. By pushing the limits of time and memory to infinity, what Alan Turing was stating about his machine was that these two variables are unimportant to what defines a universal machine. After all, if a Turing machine runs out of memory, a human operator (or another Turing machine) can come along and swap out the contents of the memory that aren't important to do the next few cycles of the calculation with blank memory so that the machine can keep running. As so long as the human operator or second Turing machine can continue to swap out the contents of the memory, the Turing machine can be said to effectively have an infinite amount of memory. This despite the fact that it only has a finite amount of memory at any discrete point in time.

[@DavidVaughan00]

But if you need some outside entity to come in and fix you up in order to keep running, surely you're not complete?

[@peteranderson037]

If the Turing machine can perform this action itself, then it is. Or, conversely, the two machines together (regardless of whether the machine is mechanical or human) make a complete machine.

[@DavidVaughan00]

Right, so either the machine can do it itself, in which case it actually *does* have access to infinite memory in the first place, contradicting the premise. Or, "the machine" you're talking about is actually machine+human, and not actually the original machine which is still not Turing complete. 

[@peteranderson037]

Another way to look at it is to imagine that the Turing machine's tape is looped around on itself. You can then program the machine to calculate some irrational. Let's use Pi as an example. If we program a Turing machine to calculate each term in the Gregory-Leibniz series or the Nilakantha series, the only information that the machine will need to know is the state of the previous term. Given an infinite amount of time, the Turing machine will have calculated every term in the series and it will thus have calculated Pi. It hasn't stored the value of Pi, but that's not the point, it has calculated every term in the series without running out of memory and thus is Turing complete. The whole point of the machine that Turing was describing in his paper was to prove that a universal machine could calculate everything that was calculable, not that it could store infinitely large irrational numbers.

[@DavidVaughan00]

+Jonathon Payne A machine with a finite tape that loops around may be able to calculate irrationals, but it cannot compute everything calculable. For example, if I want a machine that computes the reverse of an arbitrary bitstring, this finite-loop-taped machine can't do it; no matter how long it is, I'll just give you a longer bitstring. A Turing machine, by contrast, is able to complete this task.

[@wheedler]

I've seen this explained a few times, but this is the first time I think I've actually understood.

[@sidekick3rida]

The David Attenborough of computer science

[@RenegadeScooter]

I heard some people say that Baba is You, a game about changing the rules, is Turing Complete.

[@ohno6528]

I hate the assembly language, its so bad

[@TheCardil]

I hate that theoretical, abstract, academic thinking in IT. It basically doesn't move IT further in any way. Lets teach people more about everyday problems they face in real project, like structuring your code, DRY, SOLID, Patterns, UML and other tools they will use in real life. They are awesome and pretty much not understood well in general. Or think theoretically about future, not past!

[@jakejakeboom]

it's true that one doesn't need a strong theoretical cs education to br a decent software engineer or sys admin, but somebody has to be solving the hard problems (new languages/compilers, VMs, etc)

[@randomdogdog]

but turing completeness allows a developer to compare programming languages with less worry, and it only takes 5 minutes to explain secondly, abstraction is a useful tool in a programmers toolbox because they can grab that implementation and apply it to a concrete example

[@MAlgMAlg1]

If structural engineers where saying that 200 years ago, would we have our cities today?

[@boptillyouflop]

The Turing machine I guess is more useful for figuring out what's a programming language and what's not, and what problems are insoluble because you'd have to figure out the future behavior of a Turing machine without running the Turing machine to solve them (by definition impossible). I guess it gives a good guesstimate of what a smart compiler can figure out in theory and what it can't (the more it looks like a Turing machine, the more impossible it gets). But yeah for practical programming, this isn't all that useful... Kindof like something like functional programming... is there a field where functional programming is more useful than good old imperative object-oriented programming? (if anyone knows a good answer to this, please tell!)

[@TheVirIngens]

Without that our computers would be a lot slower.

[@johnnylepage681]

Out of curiosity, how is it proved that a turing machine can compute anything that can possibly be computed?

[@pedrofurla]

because that's the definition of being computable.

[@D12golden]

You should look into the Turing-Church thesis if you are interested. But spoiler alert... It isn't exactly proven. It is an informal proof, because there are a few terms that are difficult to define, such as what it means to be computable. If you try to define it, you will end up in a loop. A strange loop. More specifically, Godel's strange loop.

[@Desmaad]

Would you do a section on esoteric programming languages?

[@pedrofurla]

Turing and even Babbage, and not even a mention of poor underrated Alonzo Church.

[@D12golden]

You have to wonder what Emil Post feels at this moment.

[@f16madlion]

I understood from an MIT computer science lecture online that a program was considered "Turing Complete" when, for example, a for loop was used, or a degree of recursion used to solve a computational problem. The program can loop an infinite amount of times to meet a condition or compute output continuously, this is in contrast to the output of a program being proportonal to the length of a program. This distinction was my understanding of Turing Completeness. I would argue it has less to do with the language used but the approach and elements used to solving a computational problem. Conditionality and moving between arbitrary areas of memory would both be needed as you explained. Not quite sure i understand the infinite tape reference, is this to illustrate the potential for an infinite amount of output?

[@JayronWhitehaus]

His reaction to, "none of our computers are Turing machines" was really effing delightful.

[@unbreakablefootage]

lol the continues change between 50 fps and 30 fps (or is it 24?)

[@Computerphile]

25fps - Shot before new camera arrived :) >Sean

[@jaxwhyland]

Godels incompleteness and Turing completion makes me think Sir Roger Penrose conformal cyclical Cosmology is actually true

[@frognik79]

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.

[@seanprawn6143]

There is a game called “Turing complete” on steam that is building simple and complex “programs” using logic gates. Great fun

[@PauloConstantino167]

Am I Turing complete ?

[@sukumvit]

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...

[@sukumvit]

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...

[@fuelofmil0]

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.

[@j7ndominica051]

Does the hypothetical "tape" go backwards to allow for a loop? It doesn't seem like a real tape machine could practically auto-reverse or rewind quite as often as needed without breaking down.

[@boptillyouflop]

The tape head can move forwards or backwards. Otherwise you could never read back the data that you've written!

[@grogyan]

To me the definition of Turing completeness is that the output state is able to be relied on, given its input(s). Such a state is at least 1 bit of memory

[@ToxicJassassin]

4:43 Magic occurs & you can hear his pen even when it’s not on the page!

[@leopoldoVal]

If the amount of memory available is finite, wouldn't the computer be in Chomsky's type 3 (finite state automata or regular languages) instead of type 1?

[@aslemos2009]

I think he meant finite as a function of the size of the input. If you consider that, as our universe is finite, even the size of the input is limited, not even type 3 would be strictly correct.

[@dekippiesip]

​@aslemos2009 the universe itself could be regarded as one huge computer doing calculations all the time, applying the laws of physics on matter and energy all the time. But even it has finite capacity.

[@ianweckhorst3200]

From what I’ve learned, if it can run mind freak, it can run anything

[@tohopes]

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.

[@unvergebeneid]

"All programming languages you're familiar with [...], they're all Turing-complete." So, picking up where we left off, HTML, right? ...... That's what I thought. Well, I rest my case then.

[@orrcazz]

HTML isn't a programming language, it's a markup language.

[@unvergebeneid]

Hey *****, welcome to the channel! If you are interested in the history of my post, please watch the last two videos on the topic and pay special attention to the discussions under those videos on exactly this topic.

[@sugarfrosted2005]

+Rory Caraher That differentiation is arbitrary. HTML is Turing complete.

[@DavidVaughan00]

I'm pretty sure HTML is not Turing complete

[@unvergebeneid]

sugarfrosted No it's not! _Of course_ it's not!

[@wood-eye]

Is a quantum computer Turing complete?

[@haarmegiddo]

It basically is a Turing machine, and as such it is the same as a normal computer in terms of computation limits.

[@Eric_D_6]

Current quantum computers have way less memory than conventional computers because it's a completely different type of memory.

[@ZsoltCseresznye]

Yes (in theory), it is, and it is also an implementaion of non-deterministic Turing machine. en.wikipedia.org/wiki/Non-deterministic_Turing_machine

[@Diggnuts]

But if the promise of the quantum computer holds true and it could deal with any set of permutations in one cycle, wouldn't the virtual permutation bandwidth is like.. almost infinite!!

[@haarmegiddo]

Almost infinite only from the current human persepctive and needs. I guess in the early 80's 8GB of conventional RAM would be considered almost infinite too :D

[@SeanKD_Photos]

I'm building a computer in Minecraft using Redstone and these videos help a lot :)

[@AKSpartanhunter]

I think that has already been done.

[@none88261]

Now I know that desmos is turing complete

[@rositarabulas2347]

esatbabaataba lhaopanhdksyasakalaketelamslakratmllanglZaeyambesat porohd kyalhatkelos esat babaesGotmg 2:02

[@xoio]

Babbage, versus your Garbage

[@nyphakosi]

single instruction set computing the SUBLEQ instruction subtract A - B, store to A, if result is less than or equal to, branch to C

[@notvilaura5539]

my microwave is Turing complete. i can input anything and it will return an answer

[@victorvodka]

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)

[@dabraude]

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

[@pleasedontwatchthese9593]

Can I have a non Turing Complete computer like device?

[@enoua5222]

nope.

[@chris11119]

In principle, yes, because to be turing complete means to be general purpose, which in turn means you can solve any problem, that is solvable. non turing complete computers may include simple non programmable calculators. they can do some basic maths, but they can't solve any problem they weren't made to solve, like for instance addition and subtraction are fine but differential algebra is not.

[@enoua5222]

+chris11119 ok, true

[@pleasedontwatchthese9593]

chris11119 I like this answer

[@chris11119]

+PleaseDontWatchThese thanks :D

[@s3rgio340]

It's crazy how simple is to understand these concepts with this video. Congratulations.

[@shanewilson1160]

Never knew David Attenbruh taught cs

[@anant6778]

You just explained recursion - a turing complete lang must be able to do anything a turing machine can do

[@ingagolubeva4191]

🌹🌹🌹🌹👌

[@albiebakersmith2827]

Instead of being Turing Machines, would computers instead be equivalent to Linear Bounded Automata?

[@kgothatsontsane3119]

Wow, this is great. In all my years I have never understood something so easily.

[@finlayl2505]

Brainf**k is probably the simplest Turing complete language

[@tedchirvasiu]

Ohh, look! It's that 'HTML is a programming language' guy!

[@tedchirvasiu]

Before anyone jumps on me, it was just a joke.

[@OwenPrescott]

*jumps on him*

[@cdilipsagar123]

👍

[@francistremblay9162]

I wonder if in some cases the programming language can determine the hardware engineering and if in other cases the hardware engineering determine the programming language. If both ways are possible are their limitations and advantages.

[@oincapaz]

The reality is turing complete.

[@ikust007]

So as human we are not Turing complete since we do not have an infinite memory ?

[@tradestone100]

Tosh.0 - Web Redemption - Professor Brailsford programing language

[@ksalarang]

What I carried out from this video is that a Turing-complete machine must be able to: - have memory divided into cells where it can store instructions and data - read from and write to the memory - jump to any cell conditionally

[@lifeoftomi_]

Came here the first time because of school. Now I'm back because of Ethereum!

[@FalconGames109]

Sad to see the lambda calculus go unmentioned even though it was discovered before the Turing machine.

[@texivani]

Oh, now I understand all those "My X is Turing complete" jokes.

[@krystur9060]

this guy is awesome

[@ayushgarg70]

Please use a ball-point pen....please!

[@ikust007]

Thank you sir

[@MultiPoiu]

I have done french subtitle for the video, but dont know how it work

[@OwenPrescott]

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?

[@Thesamdeman22]

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).

[@Conenion]

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.

[@MlMZY630]

I'm extremely interested in your game now! Keep updates posted somehow.

[@crispynugget3616]

Powerpoint is turing complete Let that sink in

[@Retr0id]

Please do a video on NTRUEncrypt

[@iamstickfigure]

You should also do a video on how to prove if something is turing complete.

[@1flovera]

Is there a set of steps to proof turing completeness?

[@nO_d3N1AL]

I've been waiting for this video for a while. But I thought that another condition would be to have a loop or recursion? Also could've mentioned Turing tarpits.

[@mackncheesiest]

You can construct loops/recursion with "if" conditionals. It's a process that pretty much gets done whenever you compile a high level language into assembly, too. i.e. num = 0 loop: if num > 5 goto loopExit doStuff() num = num + 1 goto loop loopExit: doMoreStuff()

[@nO_d3N1AL]

mackncheesiest hmm I guess so but I think the video ought to have been a bit longer to explain how Turing-completeness maps to relatively high-level languages.

[@tscoffey1]

Looping is just conditional testing + a goto. Recursion is just looping with a stack.

[@boptillyouflop]

Yes, you need a loop. But of you have infinitely expandable memory, by definition you already have a loop of some kind (otherwise it would be impossible for your memory to expand infinitely so you'd only have a finite amount of usable memory).

[@klaxoncow]

A loop is simply a jump backwards. As you go through the instructions, one of the instructions later on is "jump back to instruction 2 again". So you go back to where you were and repeat all those instructions again. Including the instruction that tells you to jump backwards, so you again jump back and repeat it all again and again. Infinitely, in fact. That alone would be an infinite loop. So the combination of jumping backwards with an "if" statement that tests for a terminating condition - and then jumps out of this otherwise infinite loop - gives you a non-infinite loop. The different types of loop that you see in a high-level language are all ultimately implemented in this way. It's just a case of where you're including the "if" statement to test the terminating condition to get slightly different functionality. A "while" tests at the start of the loop and, therefore, might pass the test immediately, jump elsewhere and never enter the body of the loop at all. A "do...while" or "repeat...until" tests at the bottom of the loop, so it'll execute the body of the loop at least once. The "for" loop bases its execution on a variable. Typically a simple counting variable, so you can execute a loop X amount of times. Though C's "for" loop is very flexible and allows you to specify 3 components - an instruction to execute before entering the loop (initialisation), an expression that terminates the loop (the "if" statement) and then another instruction to execute just before you jump back for another iteration. Which would typically be initialising a variable, testing if the variable has reached X, and incrementing the variable for a simple counting loop, but C does let you place any arbitrary instruction (including none) in any of the components, so you can use it to construct pretty much any kind of loop. But, yeah, looping is nothing more than jumping backwards.

[@xanthirudha]

Is the Turing Phone Turing Complete?

[@kd1s]

Ah, goto was monster. Gosub or just calling functions in OOP is much better.

[@danmang4305]

i use return like goto.. returning functions. like.. if this: return this.. else: return that

[@Rememberedls2]

He looks exactly like Charles Babbage