4 ms·

Level 4 / total programming languages are not turing complete. Because you can't simulate every turing machine in them, only some subset that provably halts. (A

by hmry 1y ago

Level 4 / total programming languages are not turing complete. Because you can't simulate every turing machine in them, only some subset that provably halts. (And because the halting problem is undecidable, there will always be some turing machines that actually do halt but still can't be simulated because the compiler can't prove it)

kristopolous 1y ago
It's been edited since I wrote this and it's now 5 instead of 4 It didn't originally use the obscure formal idea of a "total" language
- nxnxdndndn 1y ago
  How is a total language obscure? It's a language describing total functions
  - kristopolous 1y ago
    oh I knew I was going to get this. Now I have to define obscure. Let's go! Github has two (yes, just 2) repositories referring to them: (that's nearly 0.000 000 5% of Github I hear you say) https://github.com/search?q=%22total%20language%22&type=repositories https://github.com/search?q=%22total%20language%22&type=repo... But maybe that's unfair. Let's try a software engineering encyclopedia! Ok, "Encyclopedia of Software Engineering (2011)" doesn't have it: https://archive.org/details/encyclopediaofso0001unse_m2w7/page/n5/mode/2up?q=%22total+function%22 https://archive.org/details/encyclopediaofso0001unse_m2w7/pa... Alright what about programming language text book? Well, "Programming language design concepts" (2004) also doesn't mention it https://archive.org/details/programminglangu0000watt/mode/2up?q=%22total+language%22 https://archive.org/details/programminglangu0000watt/mode/2u... What about Donald Knuth? Surely! Nope, not on the versions of his text on archive.org at least. https://archive.org/details/artofcomputerpro0002knut_u2o0/mode/2up?q=%22total+language%22 https://archive.org/details/artofcomputerpro0002knut_u2o0/mo... also https://archive.org/details/artofcomputerpro0000unse_e7w6/mode/2up?q=%22total+language%22 https://archive.org/details/artofcomputerpro0000unse_e7w6/mo... Oh let's go to arxiv. I'm sure of the ~400 CS papers that go up daily there'd be hundreds of ... oh wait, we got 5 spreading over 17 years: https://arxiv.org/search/?query=%22total+language%22&searchtype=all&source=header https://arxiv.org/search/?query=%22total+language%22&searcht... about 1 every 3 years. Alright. And thus with 5 different sampling methods all supporting the same conclusion I will support the claim that it is obscure. I know how on the internet, vibes tends to win over cited defensible evidence but I did it anyway. Maybe we can be all be adults some day.

by hmry 1y ago

kristopolous 1y ago

It's been edited since I wrote this and it's now 5 instead of 4 It didn't originally use the obscure formal idea of a "total" language

nxnxdndndn 1y ago
How is a total language obscure? It's a language describing total functions
- kristopolous 1y ago
  oh I knew I was going to get this. Now I have to define obscure. Let's go! Github has two (yes, just 2) repositories referring to them: (that's nearly 0.000 000 5% of Github I hear you say) https://github.com/search?q=%22total%20language%22&type=repositories https://github.com/search?q=%22total%20language%22&type=repo... But maybe that's unfair. Let's try a software engineering encyclopedia! Ok, "Encyclopedia of Software Engineering (2011)" doesn't have it: https://archive.org/details/encyclopediaofso0001unse_m2w7/page/n5/mode/2up?q=%22total+function%22 https://archive.org/details/encyclopediaofso0001unse_m2w7/pa... Alright what about programming language text book? Well, "Programming language design concepts" (2004) also doesn't mention it https://archive.org/details/programminglangu0000watt/mode/2up?q=%22total+language%22 https://archive.org/details/programminglangu0000watt/mode/2u... What about Donald Knuth? Surely! Nope, not on the versions of his text on archive.org at least. https://archive.org/details/artofcomputerpro0002knut_u2o0/mode/2up?q=%22total+language%22 https://archive.org/details/artofcomputerpro0002knut_u2o0/mo... also https://archive.org/details/artofcomputerpro0000unse_e7w6/mode/2up?q=%22total+language%22 https://archive.org/details/artofcomputerpro0000unse_e7w6/mo... Oh let's go to arxiv. I'm sure of the ~400 CS papers that go up daily there'd be hundreds of ... oh wait, we got 5 spreading over 17 years: https://arxiv.org/search/?query=%22total+language%22&searchtype=all&source=header https://arxiv.org/search/?query=%22total+language%22&searcht... about 1 every 3 years. Alright. And thus with 5 different sampling methods all supporting the same conclusion I will support the claim that it is obscure. I know how on the internet, vibes tends to win over cited defensible evidence but I did it anyway. Maybe we can be all be adults some day.