News for hackers. Stuff that matters.
Re:Meson 1.0 Build System by pron on Saturday December 24, 2022 @07:59AM (#34116394)
> No, user-defined functions won't make Meson Turing-complete as long as recursion is not allowed.

Turing-completeness is, itself, often a red herring. What it alludes to is the difficulty in predicting what a program would do because, in the general case, it is impossible to tell what behaviour a program in a Turing-complete language would exhibit for a particular input short of observing what it actually does. But even languages that are not Turing-complete often fall far beyond what is practically predictable. While theoretically decidable, predicting what a program written in a language with nothing but boolean variables and loops of no more than two iterations, or, alternatively, functions of boolean parameters even without recursion, is PSPACE-complete (as such a language can easily encode TQBF [1]). I.e. predicting how such a program would behave is computationally intractable, since it grows exponentially with the size of the program. Programs in such a language would also fall outside the capabilities of heuristic methods, such as SAT solvers, to tackle (SAT is merely NP-hard compared to the strictly harder PSPACE-hard TQBF).

So if your language has variables and loops (even limited to two iterations), or variables and functions (even without recursion) -- it's intractable, even though it's not Turing-complete. I don't know whether this particular language qualifies or not.

[1]: https://en.wikipedia.org/wiki/True_quantified_Boolean_formul...

Re:Meson 1.0 Build System by oldgradstudent on Saturday December 24, 2022 @12:37PM (#34119030)
The current language has loops and Boolean variables. It is trivial to reduce a TQBF formula into a Meson program.

The entire issue is a red herring.

They climbed up a tree and can't climb down without losing face.

The correct way to handle the situation is to make the change, wait for everyone to cool down, and then pretend that was their position all along.