Lua in the kernel?

Posted Sep 17, 2020 21:22 UTC (Thu) by HelloWorld (guest, #56129)
In reply to: Lua in the kernel? by excors
Parent article: Lua in the kernel?

> In practice C is not Turing complete, because it runs on systems with limited memory and limited time. Outside of theoretical computer science, Turing completeness almost never seems a productive way to think about programming languages.

Yes it's possible in theory solve the halting problem for C programs by running the program in question and waiting until it either terminates or reaches a state that it has been in before, one of which will necessarily happen because of the finite number of states that the machine could possibly be in.
But in practice, this is utterly impractical because the number of possible states, while finite, is far too big. Thinking of C as a turing complete language thus gave the correct answer in practice: it's not possible to determine in general whether a C program will halt. Considering the practical limitation of having finite memory on the other hand gives a positive answer that is complete bogus in practice. You got it *exactly the wrong way around*. Remember that next time you're trying to be a smart-ass.

Turing pseudo-incompleteness

Posted Sep 19, 2020 16:37 UTC (Sat) by smurf (subscriber, #17840) [Link]

Just to put that into perspective. The number of possible states of your computer is 2^2³⁷, if we assume 16 GBytes of RAM. That's a 456562320870-digit number, which I won't paste here for obvious reasons.

The number of distinct states a single computer can ever reach is about 2^(64*8+32+24+30), the exponent consisting of word size, #cores, and the log2 of cycles per seconds, seconds per year, and years until the Earth gets boiled into oblivion by way of the Sun going all red giant on us, respectively.

598 is about 200 million times smaller than 2³⁷.

Lua in the kernel?

Posted Sep 20, 2020 18:52 UTC (Sun) by scientes (guest, #83068) [Link] (1 responses)

LWN didn't use to have so many smart-asses. They use to stick to hacker news. Yet another consequence of the very poor situation in the US and Europe.

Lua in the kernel?

Posted Sep 23, 2020 23:18 UTC (Wed) by flussence (guest, #85566) [Link]

We can do better than feeding the troll.