Email or username:

Password:

Forgot your password?
Devine Lu Linvega's posts Post Back to profile
Devine Lu Linvega

We previously defined a programming language with the help of Turing machines.

We chose poorly.

crypto.stanford.edu/~blynn/com

6 Aug 2023 at 23:48 | Open on merveilles.town
6 comments
leah & asm & forth, oh my!

@neauoire

>

With universal machines, they explained why it’s impossible to decide if a given Turing machine ever halts

NO. NO THEY DIDN'T. :blobscream:​ see my pinned posts!​

6 Aug 2023 at 23:51 | Open on oldbytes.space
Devine Lu Linvega

@millihertz the pinned post reads like Chatin's definition of the halting problem, which is also how I understood, isn't what Ben Lynn is describing?

7 Aug 2023 at 0:01 | Open on merveilles.town
leah & asm & forth, oh my!

@neauoire no. the key bit he gets wrong is "a given Turing machine". what the Halting Problem says is that it's impossible to construct a universal function that says whether any arbitrary program will halt, and to prove this, postulates that such a function - halts(x) - has been found, and asks what will happen when we call

   p(function f) {
      if halts(f) {
         while(1);
      } else {
         return 0;
      }
   halts(p);

@neauoire no. the key bit he gets wrong is "a given Turing machine". what the Halting Problem says is that it's impossible to construct a universal function that says whether any arbitrary program will halt, and to prove this, postulates that such a function - halts(x) - has been found, and asks what will happen when we call

7 Aug 2023 at 0:14 | Open on oldbytes.space
alcinnz

@neauoire I'm not sure the halting problem is a good argument here (unless you go into Total Functional Programming), but... I do like this paradigm!

7 Aug 2023 at 0:01 | Open on floss.social
Desttinghim

@neauoire my problem with the "lambda calculus is superior" argument is that AFAIK there are no computing machines that are based on lambda calculus. Turing machines are a lot more straightforward as a basis for constructing a computing device. Lambda calculus on the other hand requires a fairly deep understanding of mathematics and mathematical notation to understand well, and doesn't have physical analogues in the same way.

Anyways, I could be wrong and just less familiar with lambdas.

7 Aug 2023 at 3:00 | Open on gamedev.lgbt
Devine Lu Linvega

@desttinghim I understand your issue with it, and I agree. I'm not sure how this is to be bridged. I'm only beginning to understand how this maps to computer hardware myself, and maybe how I could explain it to someone else, but a lot of the documentation for lambda calculus implementation out there is totally opaque - Or, I'm looking in the wrong places.

7 Aug 2023 at 3:04 | Open on merveilles.town
Go Up