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! 😅
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.
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.
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...
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.
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.
@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.
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}?
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.
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
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.
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.)
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?"
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.
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.
+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.
+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!
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.
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
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?
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.
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.
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.
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.
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.
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.
+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.
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?
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...
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...
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.
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.
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
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.
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()
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.
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).
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.
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.
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?
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.
@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.
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.
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.
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.
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!!
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
"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.
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.
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?
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).
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.
How powerful does a regex engine need to be to be Turning complete? Obviously perl's is (you can call function within the regex), but is PCRE, ERE, (and I'm guessing not) BRE...? I'm thinking any engine that has a match counter mechanism might pass the test - not sure if there is any reading on this...
Depends on what you are doing maybe? If you are doing parsing for validation, there is no way to jump backwards. If you are building a new string with back references maybe this can be considered close to the definition? There are also a number of strings that just cannot be parsed with PCRE alone (like when you need to validate some previous part of the string, multiple passes etc), requiring extra logic outside of the library (including Perl's calling a function in the regex). Turing completeness has never been proven with regex.
Ah reread your comment and get it / I agree. The closest I could come to a full (yacc/bison like) parser in my head is using named captures in an ordered dispatch table (array of kv - I think that works anyway).
Perhaps they are Turing complete given look-behind and look-ahead operators. That's the thing with Turing-completeness. Regex may fit the definition but it might take a lot of code to achieve the same thing as another language. It will almost definitely be very hard to read (even with /x). It also might be very slow or memory inefficient. All of these extra bits (speed, code size, etc) are not part of the Church-Turing thesis.
". . . 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.
Pedro Furlanetto Ah yes. The gotos. I've heard about different ranom languages being Turing Complete, like CSS even. I'd love to know how they figure it out, though. CSS doesn't have any direct programming features, though there are some branching capabilities. But what about gotos? I'd love to see a video or two showing how this is tested, and some specific examples of weird languages and _how_ they are Turing Complete.
Showing that a language is turing complete kind of easy, just write a turing machine in it. As for CSS, never heard it's turing complete, doesn't make much sense to me. But on the other hand, even the latest sql is turing complete these days.
Thomas Giles If you can hack in something like a loop of string replacements or something that calls itself recursively and lets you do the right kind of pseudo-conditionals, then you can build a Turing machine... Generally, the easiest proof of Turing completeness is interpreting a simple but Turing-complete language like Brainf*ck or SKI calculus. Even Snakes and Ladders is Turing-complete (given a board with an infinitely repeated grid section).
I've been in this game since 1976, and have never needed to know what Turing Complete means. And I'm still none the wiser. "Turing Complete" is a recent term, I've only ever heard it mentioned in the past decade or so. And as far as I can tell, these kinds of arbitrary definitions are something for computer scientists in academia to put on their exam tests, but have little if any practical value in the real world. The same as the Chomsky hierarchy, and even, dare I suggest, the ISO/OSI network model, for example. Nebulous and abstract definitions are completely irrelevant when you're a software engineer designing and implementing with hard requirements.
To allow it to perform any task. If a computer does not have an adequate amount of RAM (Random Access Memory aka "I need to create some temporary files, I will use some RAM") then it cannot perform a task. It can only perform a task that requires less than or equal to (
data takes up space on your computer, if your computer fills up all of it's memory, it has a nasty crash, we give turing machines infinite memory so they can do any problem without running out of memory and having a nasty crash e.g. running a stack (used for recursion) in real life means you worry about how big it may get, and may crash the computer
You could solve the halting problem if you had a finite tape. You can snapshot a Turing machine by saving the head position, the tape content and the current state (some q out of Q). Since both Q and the tape alphabet are finite, a finite tape size would yield a finite amount of possible snapshots. Now let your Turing machine run for that amount plus one steps and if hasn't halted yet, you know it has visited the current snapshot twice and will not halt.
They wouldn't be programming languages if you can't do anything with them. But I guess HTML and CSS can be considered programming languages, and are not Turing-complete.
Well, depends on your definition of programming languages. For me, any language that can be programmed to with some form of instructions is a programming language, such as Haskell or C. Now this definition opens up the possibility of non Turing Complete languages, such as Regex. Regex is a regular language, not Turing Complete (unless you are talking about Perl's implementation, which I don't where how powerful that is). Also with this definition, HTML is a programming language, as well as any speaking language, as such English. Now English, I would say may be Turing Complete, because we are able to describe a Turing Machine in English, even though we don't have an implementation of one.
Agda! Agda is dependently-typed, which means that it has types that depend on values. This means that arbitrary computations can occur at the type level; if the language were Turing-complete, it would be possible to send the compiler into an infinite loop by putting a nonterminating expression inside a type. In addition to being kind of a nuisance, that would render the type system inconsistent, which would defeat the whole purpose.
My brain was getting itchy thinking I remembered that about Agda but not being sure. To be fair though, there are dependently-typed languages that are Turing-complete, it's just that they're more commonly called "proof assistants". IIRC there's a C compiler written in Coq for example.
"The usual suspects: Fortran, Basic, Pascal, Cobol". Professor Brasilford is really showing his age there; it's great.
1:56 "In the late 30's . . ."
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! 😅
@@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.
And your point being?
@@WilliamFord972 What industries do you mean?
I've probably said this before but the animations are extremely helpful in understanding what is being explained!
+Ashwith Rego thanks! >Sean
is this abandon shopping cart - complete your order, well I've got infinite loop of 0 - Tuning, casual male, should make things easy
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.
I love truly enthusiastic teachers, they make everything so much more interesting.
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...
freeman account same
"You must have an arbitrary amount of memory" he says as he runs out of paper.
Loving these videos, keep it up!
+thenewboston thanks! >Sean
Buckyyy
It's crazy how simple is to understand these concepts with this video. Congratulations.
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.
Is it free to play?
@@datboi1861 no it's not but it is very much worth it imo.
@@datboi1861 just checked on Google and it should be 19.99$
@@InkDevil999 Alright. Thanks. I'll check it out.
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...
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.
neat
I'll be danged
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.
@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.
It's cool beyond belief. A machine need not actually produce sound OR graphics to be Turing-complete; just represent them through math!
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}?
No. Where's the branching?
I've seen this explained a few times, but this is the first time I think I've actually understood.
GOTO, or "How to spaghettify your code". :)
Kind regards,
Meta Custom Computers
It's also hugely useful as a fatal exception handler.
It's also hugely useful to cause the fatal exceptions with bugs on the spaghetti code
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.
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
Knuth said that Dr. Goto cheerfully complained that he was always being eliminated :)
Nice video. But when Professor Brailsford mentioned Charles Babbage, I hoped he mentioned Lady Ada Lovelace as well, but he didn't :(
Wow, this is great. In all my years I have never understood something so easily.
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.
if it's Turing complete it can run Doom
As long as they have graphics controls, yes.
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.)
Babbage is one of my favorite names. So great.
single instruction set computing
the SUBLEQ instruction
subtract A - B, store to A, if result is less than or equal to, branch to C
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
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?"
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.
i thought that Turing machine simulation was a result of being Turing complete
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.
You don't really need actual arrays though, you can use a0, a1, a2... to emulate the functionality of a constant-sized array a
sundhaug92
Ah, but for Turing-completeness, constant-sized arrays don't cut it, you need variable-sized data structures.
+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.
What?? No mention of HTML at all?? Well there is nothing for me to argue about this time.
"HTML is not a programming language, it is more like C++" - Are you triggered now?
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.
"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."
Hey, Bas, what are those pluses for?
The only real programming language is Assembly/Assembler.
+ender_scythe haha
+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!
Yay! Illuminati-bot is back!
Yaaaaayyy Illuminati!
=)))))
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.
There is a game called “Turing complete” on steam that is building simple and complex “programs” using logic gates.
Great fun
I heard some people say that Baba is You, a game about changing the rules, is Turing Complete.
His reaction to, "none of our computers are Turing machines" was really effing delightful.
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
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?
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.
Powerpoint is also turing complete
Brainf**k is also turing complete.
This video was suggested to me after watching that "Powerpoint is turing complete" clip.
@@alice_in_wonderland42 technically vanilla BF has a limited array of bytes
remove that and it would be tho
Upvote because Fortran was the first language named.
I'm building a computer in Minecraft using Redstone and these videos help a lot :)
I think that has already been done.
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.
No
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.
But if you need some outside entity to come in and fix you up in order to keep running, surely you're not complete?
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.
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.
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.
+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.
Would you do a section on esoteric programming languages?
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?
I wish I had some classes with this teacher. Damn
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...
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...
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.
The David Attenborough of computer science
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.
The tape head can move forwards or backwards. Otherwise you could never read back the data that you've written!
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
Im a cis/ computer science student and your videos are awesome. thanks
this guy is awesome
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.
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()
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.
Looping is just conditional testing + a goto. Recursion is just looping with a stack.
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).
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.
goto 6:09 -> "type 1 instead of type 0" -> *keypress 1* -> goto 0:38
program only works when the HTML5 video is selected... hmmm...
**keypress = 0** -> "theres 1 thing we keep coming back 2..."
1:16 is the thumbnail
lol the continues change between 50 fps and 30 fps (or is it 24?)
25fps - Shot before new camera arrived :) >Sean
If there are a finite number of particles in the universe, wouldn't that mean that a Turing complete machine is impossible?
'If our brains were simple enough for us to understand them, we'd be so simple that we couldn't.'Ian Stewart -
Chuck Norris built a turing machine despite finite number of particles in the universe. Twice.
Definitely.
Out of curiosity, how is it proved that a turing machine can compute anything that can possibly be computed?
because that's the definition of being computable.
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.
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?
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.
@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.
You should also do a video on how to prove if something is turing complete.
From what I’ve learned, if it can run mind freak, it can run anything
Thank you sir
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.
This is the ideal male body. You may not like it, but this is what peak performance looks like.
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.
4:43 Magic occurs & you can hear his pen even when it’s not on the page!
I just love him.
Is there a set of steps to proof turing completeness?
Please do a video on NTRUEncrypt
Thanks for making
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.
Can I have a non Turing Complete computer like device?
nope.
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.
+chris11119 ok, true
chris11119 I like this answer
+PleaseDontWatchThese thanks :D
Oh, now I understand all those "My X is Turing complete" jokes.
Is a quantum computer Turing complete?
It basically is a Turing machine, and as such it is the same as a normal computer in terms of computation limits.
Current quantum computers have way less memory than conventional computers because it's a completely different type of memory.
Yes (in theory), it is, and it is also an implementaion of non-deterministic Turing machine.
en.wikipedia.org/wiki/Non-deterministic_Turing_machine
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!!
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
I have done french subtitle for the video, but dont know how it work
You just explained recursion - a turing complete lang must be able to do anything a turing machine can do
"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.
HTML isn't a programming language, it's a markup language.
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.
+Rory Caraher That differentiation is arbitrary. HTML is Turing complete.
I'm pretty sure HTML is not Turing complete
sugarfrosted No it's not! _Of course_ it's not!
Powerpoint is turing complete
Let that sink in
Nice vid - thankyou
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?
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).
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.
I'm extremely interested in your game now! Keep updates posted somehow.
Tosh.0 - Web Redemption - Professor Brailsford programing language
Turing and even Babbage, and not even a mention of poor underrated Alonzo Church.
You have to wonder what Emil Post feels at this moment.
Is the Turing Phone Turing Complete?
So as human we are not Turing complete since we do not have an infinite memory ?
How powerful does a regex engine need to be to be Turning complete? Obviously perl's is (you can call function within the regex), but is PCRE, ERE, (and I'm guessing not) BRE...? I'm thinking any engine that has a match counter mechanism might pass the test - not sure if there is any reading on this...
Depends on what you are doing maybe? If you are doing parsing for validation, there is no way to jump backwards. If you are building a new string with back references maybe this can be considered close to the definition? There are also a number of strings that just cannot be parsed with PCRE alone (like when you need to validate some previous part of the string, multiple passes etc), requiring extra logic outside of the library (including Perl's calling a function in the regex). Turing completeness has never been proven with regex.
+Tatsh2DX so I can do (?
Ah reread your comment and get it / I agree. The closest I could come to a full (yacc/bison like) parser in my head is using named captures in an ordered dispatch table (array of kv - I think that works anyway).
Perhaps they are Turing complete given look-behind and look-ahead operators. That's the thing with Turing-completeness. Regex may fit the definition but it might take a lot of code to achieve the same thing as another language. It will almost definitely be very hard to read (even with /x). It also might be very slow or memory inefficient. All of these extra bits (speed, code size, etc) are not part of the Church-Turing thesis.
The engine you end up using has to support look-ahead and look-behind in a very flexible way. Most are very limited. Some do not support it at all.
". . . 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.
Sad to see the lambda calculus go unmentioned even though it was discovered before the Turing machine.
Instead of being Turing Machines, would computers instead be equivalent to Linear Bounded Automata?
If you include the demand for infinite memory into turing completeness then turing completeness means nothing. NOTHING in real life is ever infinite.
Pretty cool. So basically it's just if statements?
Yup. If statements and an infinitely expandable memory, and that's it!
If statements and go tos. Personally I prefer the version where it's only lambda abstractions.
Pedro Furlanetto Ah yes. The gotos.
I've heard about different ranom languages being Turing Complete, like CSS even. I'd love to know how they figure it out, though. CSS doesn't have any direct programming features, though there are some branching capabilities. But what about gotos?
I'd love to see a video or two showing how this is tested, and some specific examples of weird languages and _how_ they are Turing Complete.
Showing that a language is turing complete kind of easy, just write a turing machine in it.
As for CSS, never heard it's turing complete, doesn't make much sense to me. But on the other hand, even the latest sql is turing complete these days.
Thomas Giles
If you can hack in something like a loop of string replacements or something that calls itself recursively and lets you do the right kind of pseudo-conditionals, then you can build a Turing machine...
Generally, the easiest proof of Turing completeness is interpreting a simple but Turing-complete language like Brainf*ck or SKI calculus.
Even Snakes and Ladders is Turing-complete (given a board with an infinitely repeated grid section).
please. add the subtitles
I've been in this game since 1976, and have never needed to know what Turing Complete means. And I'm still none the wiser.
"Turing Complete" is a recent term, I've only ever heard it mentioned in the past decade or so. And as far as I can tell, these kinds of arbitrary definitions are something for computer scientists in academia to put on their exam tests, but have little if any practical value in the real world. The same as the Chomsky hierarchy, and even, dare I suggest, the ISO/OSI network model, for example. Nebulous and abstract definitions are completely irrelevant when you're a software engineer designing and implementing with hard requirements.
Dissonance: Watching this video after watching the one where he insists HTML is a programming language.
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.
@@meepisdispenser5651 js is cheating, but html + css is indeed turing complete
You can make a quine in HTML+CSS so it's fine with me
Now I know that desmos is turing complete
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.
The reality is turing complete.
Analog mechanical computers will soon make a comeback. Faith in digital security will soon end
Am I Turing complete ?
I never understod why a Turing Machine needs an infinity amount of tape/memory, really
To allow it to perform any task.
If a computer does not have an adequate amount of RAM (Random Access Memory aka "I need to create some temporary files, I will use some RAM") then it cannot perform a task. It can only perform a task that requires less than or equal to (
data takes up space on your computer, if your computer fills up all of it's memory, it has a nasty crash,
we give turing machines infinite memory so they can do any problem without running out of memory and having a nasty crash
e.g. running a stack (used for recursion) in real life means you worry about how big it may get, and may crash the computer
Because of the nature of the problem. It needs to be able to compute EVERYTHING that's computable.
Because it's an abstract mathematical model. Having finite amount of memory is an unnecessary complication.
You could solve the halting problem if you had a finite tape. You can snapshot a Turing machine by saving the head position, the tape content and the current state (some q out of Q). Since both Q and the tape alphabet are finite, a finite tape size would yield a finite amount of possible snapshots. Now let your Turing machine run for that amount plus one steps and if hasn't halted yet, you know it has visited the current snapshot twice and will not halt.
Never knew David Attenbruh taught cs
Brainf**k is probably the simplest Turing complete language
are there ANY programming languages that are NOT turing complete?
They wouldn't be programming languages if you can't do anything with them. But I guess HTML and CSS can be considered programming languages, and are not Turing-complete.
HTML and CSS without any JavaScript used to be. But with HTML5 and CSS3, that is no longer the case.
Well, depends on your definition of programming languages.
For me, any language that can be programmed to with some form of instructions is a programming language, such as Haskell or C.
Now this definition opens up the possibility of non Turing Complete languages, such as Regex. Regex is a regular language, not Turing Complete (unless you are talking about Perl's implementation, which I don't where how powerful that is).
Also with this definition, HTML is a programming language, as well as any speaking language, as such English. Now English, I would say may be Turing Complete, because we are able to describe a Turing Machine in English, even though we don't have an implementation of one.
Agda! Agda is dependently-typed, which means that it has types that depend on values. This means that arbitrary computations can occur at the type level; if the language were Turing-complete, it would be possible to send the compiler into an infinite loop by putting a nonterminating expression inside a type. In addition to being kind of a nuisance, that would render the type system inconsistent, which would defeat the whole purpose.
My brain was getting itchy thinking I remembered that about Agda but not being sure.
To be fair though, there are dependently-typed languages that are Turing-complete, it's just that they're more commonly called "proof assistants". IIRC there's a C compiler written in Coq for example.
Godels incompleteness and Turing completion makes me think Sir Roger Penrose conformal cyclical Cosmology is actually true
my microwave is Turing complete.
i can input anything and it will return an answer