Turing Complete - Computerphile
Вставка
- Опубліковано 26 вер 2024
- 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
"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
Loving these videos, keep it up!
+thenewboston thanks! >Sean
Buckyyy
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.
"You must have an arbitrary amount of memory" he says as he runs out of paper.
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
I'm building a computer in Minecraft using Redstone and these videos help a lot :)
like an actual computer?
Yeah from the subatomic level
+Kappa Kapplin 8 bits, but yeah an actual computer with memory and conditonal branching
build a Java VM inside a Java VM and run an Ackermann function on it.
I just drew a 4-bit computer for my own logic simulator. Message me if you need some help :)
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...
It's crazy how simple is to understand these concepts with this video. Congratulations.
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
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.
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!
Nice video. But when Professor Brailsford mentioned Charles Babbage, I hoped he mentioned Lady Ada Lovelace as well, but he didn't :(
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 :)
Wow, this is great. In all my years I have never understood something so easily.
if it's Turing complete it can run Doom
As long as they have graphics controls, yes.
Babbage is one of my favorite names. So great.
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.
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
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.
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.)
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.
His reaction to, "none of our computers are Turing machines" was really effing delightful.
Yay! Illuminati-bot is back!
Yaaaaayyy Illuminati!
=)))))
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
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.
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?
+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!
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?"
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?
single instruction set computing
the SUBLEQ instruction
subtract A - B, store to A, if result is less than or equal to, branch to C
There is a game called “Turing complete” on steam that is building simple and complex “programs” using logic gates.
Great fun
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
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.
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.
I heard some people say that Baba is You, a game about changing the rules, is Turing Complete.
I wish I had some classes with this teacher. Damn
Upvote because Fortran was the first language named.
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.
The tape head can move forwards or backwards. Otherwise you could never read back the data that you've written!
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?
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.
The David Attenborough of computer science
this guy is awesome
Thank you sir
From what I’ve learned, if it can run mind freak, it can run anything
I just love him.
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.
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
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.
4:43 Magic occurs & you can hear his pen even when it’s not on the page!
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
lol the continues change between 50 fps and 30 fps (or is it 24?)
25fps - Shot before new camera arrived :) >Sean
This is the ideal male body. You may not like it, but this is what peak performance looks like.
You should also do a video on how to prove if something is turing complete.
Is there a set of steps to proof turing completeness?
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.
Thanks for making
Oh, now I understand all those "My X is Turing complete" jokes.
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
Nice vid - thankyou
Im a cis/ computer science student and your videos are awesome. thanks
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.
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.
👍
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
I have done french subtitle for the video, but dont know how it work
Tosh.0 - Web Redemption - Professor Brailsford programing language
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
Please do a video on NTRUEncrypt
If you include the demand for infinite memory into turing completeness then turing completeness means nothing. NOTHING in real life is ever infinite.
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!
So as human we are not Turing complete since we do not have an infinite memory ?
". . . 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.
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
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.
Sad to see the lambda calculus go unmentioned even though it was discovered before the Turing machine.
Now I know that desmos is turing complete
Professor, are you ready to confess that HTML is not a programming language? Confess! Confess!
Never knew David Attenbruh taught cs
Powerpoint is turing complete
Let that sink in
please. add the subtitles
Instead of being Turing Machines, would computers instead be equivalent to Linear Bounded Automata?
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.
The reality is turing complete.
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)
Is the Turing Phone Turing Complete?
Brainf**k is probably the simplest Turing complete language
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).
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.
🌹🌹🌹🌹👌
my microwave is Turing complete.
i can input anything and it will return an answer
Which language is not Turing complete?
HTML.
@@B20C0it is a mark up language not a programing language
Ah, goto was monster. Gosub or just calling functions in OOP is much better.
i use return like goto.. returning functions. like.. if this: return this.. else: return that
1080p50?!? are we not worth the extra 10 fps?
If the source is recorded in 50fps, the best quality-result is to play it back at it's native 50fps. Interpolating it up to 60fps can lead to strangely looking visuals.
Kind regards,
Meta Custom Computers
lol, i was only joking. :-)