Turing Incompleteness, The Halting Problem, and Waduzitdo!

[@Truttle1]

Discord: discord.com/invite/EKPBjjUc65

[@Cliffordlonghead]

hi

[@Cliffordlonghead]

ok

[@Blaineworld]

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!

[@Tryh4rd3rr]

Lol

[@MichaelDarrow-tr1mn]

I think it's called Quine

[@Bulba413]

remember to be gay on the computer to honor alan turing or else he died for nothing

[@williamdrum9899]

Programming Socks intensifies

[@cerulity32k]

YES

[@phoenixirwin8730]

Gay?… super weird

[@MichaelDarrow-tr1mn]

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.

[@jeremychicken3339]

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.

[@rose_no]

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.

[@adamgreene9938]

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.

[@official-obama]

@@adamgreene9938 and then it passes it to halt, which expects a function with 1 argument

[@aioia3885]

​@@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?

[@rose_no]

@@adamgreene9938 That's what I'm saying. The second argument only has one argument to pass in rather than two.

[@tylerzahnke8158]

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.

[@schwingedeshaehers]

you mean like regular expressions?

[@tylerzahnke8158]

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.

[@schwingedeshaehers]

@@tylerzahnke8158 maybe look for FSM instead (finite state machine)

[@schwingedeshaehers]

@@tylerzahnke8158 so lua is no programming language?

[@tylerzahnke8158]

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.

[@sekva]

i love the attention to details, like the less than symbol in "Waduzitdo < Turing Machine"

[@EgriIstvaan]

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.

[@gregorykhvatsky7668]

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

[@EgriIstvaan]

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

[@lgasc]

_Linked List, among _*_many_*_ others, expresses their disappointment._

[@EgriIstvaan]

@@lgasc linked lists are also objects, why wouldn't they be beholden to the same rules?

[@lgasc]

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

[@cerulity32k]

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.

[@MichaelDarrow-tr1mn]

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

[@BaldiReycaster]

Happy Birthday, to Alan Turing!

[@alanbrito141]

I have never done any programming But these videos are fun

[@rpxdytx]

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.

[@Nerdmind]

I am completely convinced I will take less than 10 years until we can run doom on Conways game of life

[@clehaxze]

BUT.. HTML with CSS is truing complete. People built Rule 110.. well

[@Truttle1]

This was talking about pure HTML

[@DanielLenrd]

wait what, how?

[@clehaxze]

Yeah I know. I'm being sarcastic

[@silloo2072]

How 💀

[@gamma123-xyz]

HTML with CSS and with JS is turning complete. Probably

[@REKA]

8:21 I’m not even really a programmer but I find your vids to be so entertaining and still learn a lot

[@petarjovanovic2466]

Hi! I'm the author of the interpreter!

[@white_145]

"A terrible performance that wasn't even impressively bad." Damn that hits hard

[@samuelwaller4924]

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

[@algotkristoffersson15]

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.

[@MichaelDarrow-tr1mn]

opposite(x) = if(halt(x,x)){while(true){spin}}

[@oserodal2702]

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

[@algotkristoffersson15]

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.

[@vieilatome2257]

Yay new video! And Jr. Troopa is back!!

[@citizensnips7949]

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?

[@josephcote6120]

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.

[@donno2048]

When you state the HTML can't loop thus will always halt you're missing this option:

[@Gordy-io8sb]

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.

[@algotkristoffersson15]

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.

[@KeinNiemand]

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.

[@schwingedeshaehers]

but how do you store it to check it?

[@RedstonekPL]

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

[@antonf.9278]

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

[@official-obama]

@@schwingedeshaehers really big computer (aka turing machine)

[@schwingedeshaehers]

@@antonf.9278 but you said, computers aren't turning machines, so where do you get them?

[@cadethecrow]

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

[@aadenboy]

happy burgundy alan turning

[@m4rt_]

I make my personal websites using only HTML and a little CSS to color things, and change the sizing and placement of things slightly.

[@official-obama]

9:11 opposite takes 2 arguments, but halt probably only takes a function with 1 argument

[@ChillaxeMake]

The second argument is the input given.

[@algotkristoffersson15]

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

[@yandere8888]

oh wow i didnt know truttle was 1 month older than me i thought hes like 18 lmao

[@EdKolis]

He's been making these videos for a while now!

[@Flourish38]

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.

[@antonf.9278]

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.

[@jeremydavis3631]

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!

[@jasmijnwellner6226]

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

[@samuelwaller4924]

by that logic ASCII is a programming language

[@srgantmoomooo]

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

[@JosephOziel]

Please make a video about underload!

[@i_teleported_bread7404]

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?

[@Truttle1]

JavaScript

[@randomazzy11]

OMG YAY I LOVE YOU TRUYTTLE

[@MichaelDarrow-tr1mn]

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

[@donno2048]

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

[@tediustimmy]

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.

[@nyphakosi]

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

[@photophone5574]

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

[@urisinger3412]

in the theoretical sense is also not turing complete, as pointers are bounded

[@JonGallon]

8:23 Because yes. Also, reptiles, lots of reptiles.

[@user-yn1oi6iv1f]

7:50 should've used binary search

[@Lixxide]

Jr Troopa went from anoying to menace

[@kin98100]

There are technically template tags im html which one could describe as am variable

[@IceMetalPunk]

Kind of, but you can't do anything with them without JS. (Data attributes are similar.)

[@yb1_]

my birthday is 1 day before Alan Turing’s birthday

[@SparkDragon42]

TIL Jr Troopa is older than me (unless you count its European release as I'm European)

[@Truttle1]

He’s older than me in all versions except Chinese lmao

[@EdKolis]

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

[@SparkDragon42]

@@EdKolis truttle's birthday is July 26, 2002. So you're right, between 2001 and 2004 :D

[@EdKolis]

@@SparkDragon42 I just looked up when the game was released because I was curious 🙂

[@lilyzheng2322]

Jr Troopa’s cool

[@fdsKedi]

"HTML isn't turing complete" sadly sitting in the corner

[@etheraelespeon1986]

Ooh, that lang handles conditionals like Shenzhen I/O!

[@yglyglya]

woohoo

[@unchaynd7266]

babe wake up, new Truttle1 video dropped

[@mathe42]

Fun fact: HTML + CSS is Touring complete...

[@chescocooks7697]

I HEARD THAT WONDER BOY REMIX

[@sameer1321]

kind of late but i think i'm here before victor tran?

[@nebularzz]

hey

[@kstudios4046]

Can you do 👀

[@unchaynd7266]

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

[@obviousalexc]

"OH javascript isn't that bad" - Javascript programmer I am still salty about them deciding not to add operator overrides.

[@TheTriggor]

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.

[@gamma123-xyz]

alan has birth

[@moltony]

yooo

[@thisisaplaceholdernamedont6980]

0:07 python is also kind of garbage, the more you think about it

[@Truttle1]

Python good

[@IceMetalPunk]

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

[@YEWCHENGYINMoe]

13h ago

[@EggJEYT]

44th

[@tooru]

this whole unnecessary cartoon sht just makes me cringe