Can we do without while loops?

[@applimu7992]

This is another example of something called a diagonal argument! much like Cantor's diagonal argument and the proof against the halting problem. I love it!

[@hiredfiredtired]

I was just thinking about the ackermann function the other day and didn't really understand terms like "primitive recursive", this video was a lifesaver! I am surprised you don't have that many subs

[@tanchienhao]

The beginning of recursion theory! Partially recursive functions are roughly speaking the functions that can be computed using for loops, while general recursive functions are functions that can be computed using while loops

[@SimGunther]

Technically you could do everything exclusively as a "for loop". YES, even blocks that only have one or zero iterations.

[@DaedalusCommunity]

Ackermann does not like this item

[@DaedalusCommunity]

Yes, it is! But at 2:31 I mentioned how the programs that "mess with the index" are banned from our definition, and for(; true ;) certainly does mess with the index (it does not increment it!)

[@ben_jammin242]

My event listener disagrees

[@coollifebox09]

i really like your content i hope to see it more often tho

[@DaedalusCommunity]

I'm really busy with university, so I can't upload very often.. Still, I'll try :)

[@harrypanagiotidis7370]

A for loop is just a tidy while loop. Fight me.

[@DaedalusCommunity]

It's a while loop that quits 😢🫂

[@garklein8089]

A while loop is just a tidy goto. Fight me.

[@DaedalusCommunity]

@@garklein8089 This

[@TheOzumat]

do { //stuff } while (youCan); how is that not tidy? :O

[@crossscar-dev]

PLEASE BRING BACK THE OS SERIES

[@Galactipod]

What font do you use?

[@DaedalusCommunity]

Computer Modern for the text, Consolas for the code, Comic Sans for the memes

[@atomgutan8064]

This mathematical proof is probably totally unrelated to programming but I think you can just replace while (condition) {code} with for (; condition;) {code}

[@DaedalusCommunity]

Yup, in practice you can do that. In the context of the video, that would be considered "messing with the index", so it's not allowed :)

[@Luycia]

The for loop in the isPrime function should run to i less equal sqrt(n).

[@DaedalusCommunity]

That's right :)

[@Aurora12488]

Trivially, a program that increments a counter until it receives an interrupt to stop it needs a while loop (or functional equivalent). That interrupt could come at any time, for any reason.

[@DaedalusCommunity]

Sure, but a program that may receive an interrupt is not an "interesting" program, because the interrupt may never come and the program may never halt :)

[@chrispence8352]

Well I’ve tried using your shell script for setting up the cross compiler for i386-elf target but still have the i386-elf-gcc command not found error after building. Is there anything that might’ve missed in your shellscript

[@fantasypvp]

Ive been programming in rust for over a year and since moving to it from python i dont think I've ever needed to use a while loop, you can just use break when you want to exit out of the loop.

[@DaedalusCommunity]

Rust

[@nebularzz]

Rust@@DaedalusCommunity

[@kvelez]

Cool

[@haarmegiddo]

Since we know the size of N, I really don't see a reason why we couldn't implemented Ackermann function with a for loop... what am I missing?

[@DaedalusCommunity]

The intuition for why this is not the case should be the following: To write A(n,x,y), with fixed n, you need at least n nested loops. So to define the function in general, you would need infinitely many nested for loops, hence you cannot do it with for loops. Then again, the actual proof is a bit more complex; you'll find it in the description :)

[@devrim-oguz]

While loops run faster in embedded systems and use less RAM. Not always though.

[@ContentBeachYoga-cw1op]

ackermann function

[@jean-lucportner8635]

In C one could just emulate a while loop by using goto i.e. start: if(...) { ... goto start; } Technically you did not exclude that I believe. Although it basically is cheating.

[@devrim-oguz]

But using goto statements is a really bad idea with the modern day compilers

[@DaedalusCommunity]

Yeah that's definitely cheating

[@DaedalusCommunity]

@@devrim-oguz Most times, yes. There are some use cases, e.g. breaking from several nested loops at once

[@oj0024]

It's non obvious that the C language (in the sense of the abstract machine) is even turing completed, and I'm not fully convinced of it my self. Consider that the size of pointers is finite (sizeof(void*) is a constant expression) and they must be able to convert to and from uintptr_t. The size of pretty much any memory has a finite upper limit for any given implementation of the abstract machine.

[@DaedalusCommunity]

No real life implementation of C, or any other programming language, is Turing complete. This was kind of a shocker when I was told in computability class, but it makes sense; memory is finite, so of course you can't simulate a Turing machine. One thing that is very much certain is that C itself, as a language, is Turing complete, because it is a superset of a WHILE language (and because it's very simple to simulate a Turing machine in C).

[@oj0024]

@@DaedalusCommunity but simulating a turing machine requires infinite memory, which arguably isn't doable because every implementation (even a purely theoretical one, that uses an existing Turing machine) must have upper bound on the maximum amount of addressable memory.

[@DaedalusCommunity]

@@oj0024 Why would that be the case?

[@oj0024]

@@DaedalusCommunity A turing machine needs ibfinite memory, because otherwise you can trivialy solve the halting problem for it using a real turing machine. C has a upper bound on addressable memory, because sizeof pointers can't change at runtime.

[@nebularzz]

cant you just get yourself a computer that can handle numbers infinitely well and use a for loop that stops once you reached the number after all the other ones

[@DaedalusCommunity]

Can't believe I didn't think of that lmao

[@dying476]

I think there's a mistake in the proof. When you define what list[n] is, the definition isn't include "they can call another list function." There are 2 reason why this rule shouldn't be included. 1. This will cause "circular definition." You can't define list[n] to be "those who can return in a finite time and call another *list function*," or it will be defined by themselves. 2. Consider this function: input n; return list[n](n); This is the function that appeared in video but without "+1" in return statement. If a list function can call another list function, then the above function should also be one. Assume the index of it is x. Then we give x as an argument for it. It will return list[x](x), and it's just itself, so it will be in a recursion for infinite time. Obviously, an infinite recuring function isn't an interesting function, so it isn't a list function, either. Due to the two reasons, a list function shouldn't call another one, so the "weird function" in the video isn't in the list. Therefore, the proof in the video is invalid.

[@DaedalusCommunity]

I don't understand what you mean. I define list[n] as "the n-th program that does not use while loops, according to some arbitrary enumeration". The function f(n) = list[n](n) + 1 fits the definition of computable function (because it calls a computable function and applies a computable operation to it), yet by a diagonal argument it is shown not to be in the list. The proof is quite standard, and it is mentioned in several books, among which Godel Escher Bach by Hofstadter, who used a slightly different formalism for the proof: en.wikipedia.org/wiki/BlooP_and_FlooP. The proof also relies on the fact that the set of (finite length) programs that do not use while loops is countable (i.e. it is in a bijection with the naturals), whereas the set of countable functions is not. Therefore, these cannot be in a bijection, hence there are some computable functions that cannot be expressed without using while loops. Edit: Here is a further example of a diagonal argument: en.wikipedia.org/wiki/Cantor's_diagonal_argument Further edit: I probably now understand what you mean. You are saying that making it so that a function in the list can call another function in the list would make the definition circular. It is an understandable objection, and the reason why it is not valid is a bit deep. - As mentioned before, we define the list[n] as "the n-th program that does not use while loops, according to some arbitrary enumeration". - Once we have defined the list, we can define the function f(n) = list[n](n) + 1, and we can ask whether or not such a function is or is not in the list. The one key point is that we're asking *if there is a function in the list that is equal to f*. In order for two functions to be equal, they need not have the same "body", they just need to return the same output whenever provided with the same input. As an example, the two functions "g (x) = sqrt (x^2)" and "h(x) = abs(x)" are not written in the same way, but are **the same function**. So, the function that we are looking for in the list is not one that "calls a list element", but one that behaves in the same manner as the function f(n) = list[n](n) + 1, and is not written using while loops. Is it clearer now?

[@dying476]

@@DaedalusCommunity Thanks for you explanation. Now I know where I misunderstood the proof. I mistook the same functions for those with the same body, so i mistakenly thought there's some list[n] call itself and cause infinite recursion. You explained very well. I'm very grateful.

[@DaedalusCommunity]

@@dying476 thanks! Your question was very good, too!

[@christopheriman4921]

At 3:50 haven't you actually shown that you can't list the number of "interesting" programs or in other words there are an uncountably infinite number of these programs and not that you can't write all of the programs without while loops? I am not saying that your conclusion is necessarily wrong but I think you need a bit more reasoning than just that you can't count the "interesting" programs.

[@womi1141]

I guess that KZbinr Winderton stole the format from you

[@womi1141]

link: youtube.com/@wndtn

[@mad_circuits]

Just use for(;;) 😂

[@DaedalusCommunity]

As I pointed out in other replies, for (;;) messes with the index (does not increment it) so it's not considered