Turing Incompleteness, The Halting Problem, and Waduzitdo!
HTML-код
- Опубликовано: 7 фев 2025
- Waduzitdo is a programming language that isn't Turing complete. This is because the only way it can loop is if a single boolean input by the user is true, and it can only jump back to the most recent input even if it does loop. This means it can't do very much. But, if we use a Turing complete language like Python, we can determine if a Waduzitdo program halts or not, which you cannot do for any Turing complete languages.
LINKS:
Waduzitdo Esolangs.org: esolangs.org/w...
Python Interpreter: github.com/JP2...
Python Interpreter Fork: github.com/Tru...
My Programs: github.com/Tru...
HTML meme: / html_isnt_a_programmin...
Troopa Image: / ttyd_remake_looks_like...
MUSIC:
SimCity 3000 - Uptown Down
Wonder Boy: The Dragon's Trap - Monster's Lair
Paper Mario - Jr Troopa Theme
Kevin MacLeod - Meatball Parade
Paper Mario: The Origami King - Swan Lake Remix
Paper Mario: The Thousand Year Door - Rogueport Sewers
Phoenix Wright: Ace Attourney - Cornered
Super Mario RPG - Seaside Town
Discord: discord.com/invite/EKPBjjUc65
hi
ok
i made an interpreted language called cat in which the only operation is to print the source code of the program. i actually went and secretly installed the interpreter on all unix like systems while you were all asleep!
Lol
I think it's called Quine
Change the title to Quine because that’s what a Quine program does
my favorite part about the conway's game of life thing is that it... has graphics. They're called metacells. You can put the input on glider strames going into the Turing machine running the game.
If someone makes a playable doom port (You control the inputs by making gliders) on game of life, they clearly don't have a life of their own.
Happy birthday Turing! I wonder what he would have thought of the existence of Turing incomplete languages! I mean ones that are trying to pass as programming languages like Waduzitdo is, not languages like HTML that aren't even pretending to be programming languages.
you mean like regular expressions?
I've been hearing people say that lately, and I don't get it! Yes, I know what regular expressions are, there's a chapter about them in any JavaScript book worth its salt, but still, I only think of regular expressions as a feature of another programming language; I associate them with JavaScript, but I think they've been used in Python, and given the text processing nature of Perl, probably that too. But I don't get this culture around regular expressions as a language. To me, regular expressions are part of a language. Like a data type or object type. I just started hearing in the past few years all this talk like it's a language and I don't get it; I was twelve years old when I learned regex, that's fifteen years ago now, but I just saw it as part of JavaScript, not its own language.
@@tylerzahnke8158 maybe look for FSM instead (finite state machine)
@@tylerzahnke8158 so lua is no programming language?
Who said Lua wasn't a language? The only thing I know about regex is that it's a feature! I see it in the tables of contents of JavaScript books, Python books, etc. as a language feature, not a language.
i love the attention to details, like the less than symbol in "Waduzitdo < Turing Machine"
remember to be gay on the computer to honor alan turing or else he died for nothing
Programming Socks intensifies
YES
Gay?… super weird
"A terrible performance that wasn't even impressively bad."
Damn that hits hard
When you had the halting problem code on screen, you showed `opposite(opposite, opposite);` (9:23), implying that `opposite` only takes one argument when it actually takes two.
Not too big of a deal, but I figured somebody ought to point that out.
Actually opposite is supposed to have 2 inputs, one is the function it's testing and the other is the value to run the function on. In this case he's running it on the function itself, which is a little weird, but it does need two arguments.
@@adamgreene9938 and then it passes it to halt, which expects a function with 1 argument
@@adamgreene9938but halts expects a function with one argument so opposite should really be a function of one argument f that then calls halts(f, f), right?
@@adamgreene9938 That's what I'm saying. The second argument only has one argument to pass in rather than two.
@@rose_noexcept halts needs to know the what input it’s input receives.
Because otherwise inputting à truth machine into it would break it.
0:06 for C, I have once read a very uncovincing, techical and nitpicky argument in some stackoverflow thread about why it is not turing complete.
I do not remeber some things clearly, so I am sorry if I say some incorrect things.
The argument was as follows: in order for a programming language to be turing complete, it has to be able to simulate a turing machine. A turing machine, among many things, consists of a tape of indefinate size. In C, the size of objects, for example, arrays is stored in the size_t type, which can only be a finite number, and its size is stored in SIZE_MAX. Because of this, you could not create a turing machine's tape in C, as if you had more than SIZE_T values on that tape (which it could be, its size is indefinite), you could not be able to simulate it inside of a C program.
Nothing is preventing you from writing functions like int get_memory(BigInteger *o, size_t size, char *data) / int set_memory(BigInteger *o, size_t size, char *data) that will then access whatever boundless storage system you have and copy the data between it and system ram
@@gregorykhvatsky7668 happened to find that thread while searching "c turing complete", they dismiss external storage as not being managed by C (unlike the system ram, the heap)
_Linked List, among _*_many_*_ others, expresses their disappointment._
@@lgasc linked lists are also objects, why wouldn't they be beholden to the same rules?
@@EgriIstvaan There is actually no such thing as a Linked _List object_ in C;
instead the object you have is a Node object featuring - additionally to their datum - some pointer field "linking" to some other Node.
As such, each Node has a finite size. Thus, Lists resulting from "link" chaining are not bound by size.
I have never done any programming
But these videos are fun
Note that a markup language can still be a programming language, even a turing complete one. It's just that most of them aren't, including HTML.
Happy Birthday, to Alan Turing!
I am completely convinced I will take less than 10 years until we can run doom on Conways game of life
I swear I feel like you were trying to mess with our heads in your demonstration of the halting problem, cause that pseudocode is *cursed* .
Hi! I'm the author of the interpreter!
From the thumbnail it made me say, "Hey! That's Pilot!" We had seen the article in BYTE and said we can write that language. And we made a Pilot interpreter in HP2000 BASIC. The non-computer people who tried it thought it was pretty fun. No real way to hold a lot of text in a program tho, so we ended up with something that smelled a lot like EDLIN.
1:34 When I realized the page was made by you for the express purpose of demonstration in this video, and it wasn't a piece of ancient internet history, it felt like stepping on a rake and it hitting me in the face. I really need to become less gullible.
Opposite(opposite,opposite) is just an infinite loop science we are runing opposite on a copy of opposite that runs on a copy of opposite running on an empty program, and empty programs don’t loop.
Yay new video!
And Jr. Troopa is back!!
I make my personal websites using only HTML and a little CSS to color things, and change the sizing and placement of things slightly.
9:27 But `opposite given some input` is different from `opposite given opposite, which is then given some input`. If `opposite given some input` halts, then `opposite given opposite that is given that same input` loops, both of which can be predicted. I'm definitely missing something about the Halting Problem.
it is that the opposite function is written a bit wrong. halt only takes one-input functions. just slightly alter opposite so that it takes one input and opposite(opposite) still paradoxes
@MichaelDarrow-tr1mnexcept halt can’t possibly only take one input because some programs, for example the Truth-Machine machine program may or may not halt depending on its input
@MichaelDarrow-tr1mnno it doesn’t, because opposite with no input (which is the input halts will get in your poorly written context) just always enters an infinite loop because it demonstrates the opposite behavior relative to an empty program.
Therefore Opposite(Opposite) is simply a No-Op
BUT.. HTML with CSS is truing complete. People built Rule 110.. well
This was talking about pure HTML
wait what, how?
Yeah I know. I'm being sarcastic
How 💀
HTML with CSS and with JS is turning complete. Probably
When you state the HTML can't loop thus will always halt you're missing this option:
9:07 except you can’t just input opposite into itself, because then the version of opposite you use AS input doesn’t itself have any input. You would need to do opposite (opposite, opposite(opposite, opposite(opposite,opposite…))) using infinite opposites which you can’t do.
opposite(x) = if(halt(x,x)){while(true){spin}}
hey truttle i made a programming language that makes HTML turning complete... kind of. obviously not really because it's not HTML, but at least it looks like HTML. its called EHTML, its the first one I've made, and it was a lot of fun making. anyway the point being you inspired me to make it by getting me into these stupid languages. you're a real one, peace
2:31 react propaganda
It depends on how you define "interactivity", but plain, modern html+css can be plenty interactive (you'd be surprised). You can send and set cookies in HTTP headers to maintain state (plus the path and GET parameters), and do anything else you want on the backend.
If you define "interactive" as "100mb SPA" then yeah you need JS. But then the question is do you really need that lol
11:35 Except if there’s a program that jumps back on a match, and the user repeatedly inputs the correct answer, then it does go into an infinite loop. Nothings stopping the user from inputting the same thing repeatedly.
The complete comprehensiveness required to write a functioning waduzitdo program sorta reminds me of the spreadsheet that they used to prove that dragster wasn't possible in 5.51 seconds...
What I'm saying is, it would be a fun exercise to generate a waduzitdo program that is able to simulate all games of dragster that are less than 6 seconds of input long, frame-by-frame.
Also, I wonder how much computation you could allow in a language while still keeping it turing incomplete? I guess you could maybe separate it into a phase where loops are allowed and inputs are gathered, and a phase where loops aren't allowed and basic computations are performed. And maybe you could have multiple of those, so long as no variables carry over between sections? You might be able to do something a LITTLE more useful with that.
You can have a language with loops. As long as the amount of iterations is defined before entering the loop and can't be changed while inside the loop it will always halt.
Example: If you have a python program that only loops on like `for i in range(n):` and don't do recursion it will always halt.
oh wow i didnt know truttle was 1 month older than me i thought hes like 18 lmao
He's been making these videos for a while now!
happy burgundy alan turning
How do I send you money and how much of it do I need to send you to convince you to make a video that explores the code of the Python interpreter and discusses what can be added to make it Turing Complete?
there's a bit of problem with the video..., the "halting problem unsolvable" thing you mentioned... it doesn't work. halt only takes functions with one input. just make opposite(x) be "halt if and only if not halt(x,x)" and then opposite(opposite) is a paradox
Can’t you make a HTML page loop using the ”INCLUDE” tag to include it in itself
i love you, can u make a video on racket? it is also an old language meant to be used for teaching programming... it is a very cool and interesting language :)
You have a small mistake in the explanation about why turing complete languages can't create a halting predicting function. In order for this construct to work you need the halting function not to take an input (only the function) as it checks of there is an input for which the function bever halts
Please make a video about underload!
9:11 opposite takes 2 arguments, but halt probably only takes a function with 1 argument
The second argument is the input given.
@@ChillaxeMake yes but then the instance of opposite used in halt itself only has the input of one copy of opposite therefore doing the opposite of what a copy of opposite with no input does. Therefore science an empty program doesn’t loop opposite (opposite, opposite) translates to opposite (opposite, loop) which translates to opposite (doesn’t loop) which translates to loop.
reminds me of the language of the zachtronics game Shenzhen I/O
prefixing an instruction with + only runs it if the most recent comparison was true, and similarly - for if it was false
I would argue that every markup language is, technically, a programming language: it tells an interpreter (which is almost always a Web browser in the case of HTML) how to accomplish a task (in this case, displaying a webpage). Of course, without CSS, it's neither Turing-complete nor general-purpose, but not all programming languages are (Waduzitdo is a good example of this). The debate is just a disagreement about the boundaries of an imprecise definition, just like arguing about whether a taco is a sandwich.
This got me thinking, though: when it's said that HTML isn't Turing-incomplete, that doesn't include when hyperlinks are used, does it? Theoretically, given infinite storage space, you could encode every possible state of a given Turing machine (both the tape and the state machine) in the name of an HTML file, and each HTML file would contain a link to whatever state follows it. The mathematical definition doesn't care where the impetus for continuing the calculation comes from, so it should be fine, technically, for it to require a user to repeatedly click on whatever link appears on the screen (like turning the crank of Charles Babbage's analytical engine). There can be multiple links per page if we want to take user input (mathematically unnecessary but very important in practice). And the resulting program could even include graphics and sound!
So, for example, I can implement an addition quiz program like the one from the video with these HTML pages:
guess.html:
2 + 2 = ?
0
1
2
3
4
5
6
7
8
9
wrong.html:
Wrong answer! Try again.
right.html:
Correct! 🎉
Notice that guess.html and wrong.html form a potentially infinite loop (a mark of Turing-completeness) with different behavior depending on user input (which is necessary for a general-purpose programming language).
This program only needs to remember between 1 and 2 bits of data because it only has a total of 3 states. But as long as we have an unfathomably immense amount of storage space and (rough estimate) a few millennia to write out every possible state transition, it should even be possible to make pure HTML with hyperlinks run a single-stepping version of Doom!
Potentially infinite loops aren't a mark of Turing-completeness in themselves (after all Waduzitdo has potentially infinite loops and can implement the same algorithm as guess.html and it isn't Turing complete). The technique that you're proposing is that of finite state automata (the same as Waduzitdo).
by that logic ASCII is a programming language
Actually no real conputer is Turing complete becouse computers have finite memory, ehich means for every real computer the halting problem is decidable becouse you know it dosn't halt as soon as the same exact sate of everything repeats.
but how do you store it to check it?
turing complete doesnt mean its a turing machine
it means that it can compute everything thats computable
also we dont call computers turing complete just programming languages
@@schwingedeshaehers Just take you turing machine and store all the states you have seen so far at on the infinite tape.
You actually just need enough for 2^n bits where n is the number of bits on disk, in ram, in registers and wherever else the computer can store information.
@@schwingedeshaehers really big computer (aka turing machine)
@@antonf.9278 but you said, computers aren't turning machines, so where do you get them?
NJ: yet another go to statement for a languages that uses letters and colons to write code.
in the theoretical sense is also not turing complete, as pointers are bounded
OMG YAY I LOVE YOU TRUYTTLE
I've seen a lot of games on Armour Games that are tagged as "HTML games". If HTML isn't a programming language, how were they made?
JavaScript
I ran Waduzithalt on numberguess and it told me that it doesn't halt. This is true and false. If I recall my CS correctly, we must always treat the input to a Turing machine as finite, because we pass it to the machine as the tape's initial state. So, this program runs to an end-of-input condition. However, the language underspecifies what to do: your python interpreter throws an exception and terminates. A naive C implementation would pass EOF on and run forever.
I remember coming up with something that wasn't turing complete but was kind of an esolang. It was like the brainfuck equivalent of sql/database languages
There are technically template tags im html which one could describe as am variable
Kind of, but you can't do anything with them without JS. (Data attributes are similar.)
8:23 Because yes.
Also, reptiles, lots of reptiles.
woohoo
Jr Troopa went from anoying to menace
Ooh, that lang handles conditionals like Shenzhen I/O!
my birthday is 1 day before Alan Turing’s birthday
Yeah the thing about HTML is that it is representing data, not logic. So it's like a Turing Machine minus the control unit... i.e., just the tape. At least that's my understanding of it
TIL Jr Troopa is older than me (unless you count its European release as I'm European)
He’s older than me in all versions except Chinese lmao
So you were born between 2001 and 2004, then. About the same age as my little sister, and my nephew (my wife has several older brothers, just like my sister!)
@@EdKolis truttle's birthday is July 26, 2002. So you're right, between 2001 and 2004 :D
@@SparkDragon42 I just looked up when the game was released because I was curious 🙂
7:50 should've used binary search
Jr Troopa’s cool
babe wake up, new Truttle1 video dropped
"HTML isn't turing complete"
sadly sitting in the corner
I HEARD THAT WONDER BOY REMIX
Fun fact: HTML + CSS is Touring complete...
Can you do 👀
But a program that can take input is completely useless
kind of late but i think i'm here before victor tran?
"OH javascript isn't that bad" - Javascript programmer
I am still salty about them deciding not to add operator overrides.
This language doesn't look beginner-freindly at all. Might be nice to make a Hello World, but anything more complex would get frustrating. I'd rather start by learning C than whatever this is.
hey
how dare trash talk about javescipt!1!!1!
alan has birth
0:07 python is also kind of garbage, the more you think about it
Python good
@@Truttle1 Until you need threading, and you realize Python threads don't actually act like threads because of the GIL 😜
I'm a JS and Python programmer, I like both, but you've got to admit they both have their quirks.
yooo
13h ago
this whole unnecessary cartoon sht just makes me cringe
The word ”Cringe” should not exist.
Please never use that word again, it sounds stupid
44th