mmarx

> I don't understand why you people act like you're stumped by literally, literally page 1 of computer science.

… and yet you didn't stop for a moment to consider that in a field as fast-moving as computer science, a concept which might not have had a formal definition in 1967 acquired one in the past 59 years? See, for example, Sipser's Introduction to the Theory of Computation, which has an entire section (3.3 in my 1997 print) titled “The Definiton of Algorithm”.

It's already past midnight in New Zealand, e.g.

In multi-user mode, Nix uses dedicated build users to write to the store. There is also single-user mode, but that also doesn't require a world-writable store.

> Theoretically, we could also go for finding the semantically equivalent C code. However, last time I researched, checking semantic equivalency is a very complex problem. I think it was NP hard.

Already deciding whether two finite automata decide the same (regular) language is PSPACE-complete; it's undecidable for anything that can decide arbitrary context-free languages (which C programs can clearly do).

This machine has 8 states, so (for actual Turing Machines with an unbounded tape) you'd be looking at BB(8). However, since the tape can only store 24 symbols, the machine only has 8 (states) * 4 (tape symbols) * 24 (tape length) = 768 different configurations. Thus, any program will either terminate in at most 768 steps, or loop indefinitely.

Since the model tape isn't actually infinite, this machine has a finite state space, and termination is therefore decidable. No Turing Award to obtain here …

https://github.com/KFearsoff/nix-drama-explained has a good summary of what the contention is about.

Yes, technically you'll also get a MediaWiki instance there, but the point is really to offer Wikibase (which is a set of extensions upon MediaWiki), the software behind Wikidata.

> Before the phaseout started, nuclear contributed more than 20% to electricity generation.

That's true, but also quite meaningless. Before the nuclear phaseout started, renewables contributed less than 7% to electricity generation, now it's over 56%, so it more than compensates for the missing nuclear generations. Furthermore, replacing coal with nuclear is not easily done, since most coal plants also generate heat, whereas none of the nuclear plants did.

> Earth just experienced its hottest 12 months in recorded history and it was really incredibly poor decision making to start shutting down nuclear power plants while still burning coal.

None of the remaining reactors had usable fuel left, even just acquiring new fuel would already take 12 or more months (besides, all of the remaining reactors were already several years overdue on safety inspections). The decision to phase out nuclear power has been made well in advance of those 12 months: originally in 2002, partially pushed back in 2010, then finalised in 2011, and again pushed back (by 3.5 months) in 2022. The poor decision making is not phasing out nuclear power, the poor decision making is not also phasing out coal and pushing renewables from at least 2011 onwards.

> Another example of poor decision making is Germany which decided to start shutting down nuclear power plants while they were still burning coal. So last year hard coal and lignite still produced 35.3 percent in German power production (compared to 35.2% from renewables. (https://www.cleanenergywire.org/factsheets/coal-germany). Before the phase out of nuclear, it generated about 25% of the electricity. It is all really hard to believe...

That article is from January 2023, so the numbers in there are 2022, not last year, and even then it says that nuclear produced only 11.7%. In any case, comparing to the official numbers[0], those seem to be closer to the 2021 numbers than the actual 2022 numbers: 31.3% coal, 6% nuclear, and 44% renewable. For 2023, coal was down to 26.22%, nuclear (which was only phased out in April) was down to 1.5%, and renewables were at 56%. Nuclear has not contributed more than 20% to electricity generation since 2011[2].

[0] https://www.destatis.de/EN/Themes/Economic-Sectors-Enterpris... [1] https://www.smard.de/page/home/topic-article/444/211756 [2] https://ag-energiebilanzen.de/wp-content/uploads/2023/10/STR...

from the linked YouTube video:

> This is the second time I've successfully tested this on a Class 800. For some reason this time I seem to have actually confused the toilet door controller enough that it decided "screw this" and went into out of order mode, which didn't happen the previous time.

So, yes, the author _did_, in fact, disable the door.

Ah, thanks, that was indeed what I was missing.

From the truth table, subtraction is clearly truth-preserving, so it cannot actually be functionally complete. What am I missing?

Even though halting is generally undecidable, there are still large classes of programs for which you _can_ show termination. If you reject every program for which you cannot show termination, you will also reject some programs that terminate, but you never need to worry about halting again. Indeed, languages such as Idris do exactly that. [0]

[0] https://en.wikipedia.org/wiki/Total_functional_programming

Mixing tabs and spaces is a TabError in Python 3, so this would definitely error today.

> It would be absurd to compare unary and binary addition relative to the same numeral length.

Why? The Turing machine has no concept of numeric values, it only knows about the length of whatever the input is.

> Adding one million to one million is simply much faster for binary addition than for unary addition, even if unary addition has better complexity relative to its own encoding than binary addition has to its encoding.

From a complexity standpoint, adding one million to one million is O(1), irregardless of the encoding.

> We are interested in complexity relative to the numerical value, not in the length of their respective encodings.

But the complexity relative to the numerical value is not even well-defined, since it _depends_ on the choice of the encoding.

> By the way, as the Wikipedia piece notices, the binary addition algorithm is O(log(n)) in time _relative to the value_, while unary addition is presumably O(n) relative to the value (just writing the numeral out alone takes O(n) steps). So the time complexity is in fact better.

It really is not better. Time complexity is _always_ measured relative to the length of the input, and for binary encoding, the length of the input is O(log(n)), so, taking O(log(n)) steps for the addition is linear, same as the linear time needed for adding numbers in unary encoding (which is basically just copying the input to the output).

> Moreover, only in this case makes a comparison even sense, since we are comparing the same values in both cases, while for the numeral case we would be comparing the lengths of two different types of numerals, apples to oranges.

But _the numeral is not the input_, its _encoding_ is. This is really the whole point, and it is _precisely_ because you get different complexities for different encodings.

> That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value.

It really is not, because complexity is fundamentally a function of _the length of the input_ (specifically: it measures how the runtime (or space usage) grows with growing input). If you have longer input, your Turing machine can spend more time to compute its answer. Also note that this assumes that _the input_ is encoded in unary, if you get binary input and need to spend time and space to convert it to unary representation, sure, that will lead to an exponential blow-up.

Actually, an algorithm working on unary input tends to have better computational complexity than an algorithm working on binary input: an algorithm that is polynomial in the numeric value will be a polynomial algorithm on unary input, but an exponential algorithm on binary input. Such algorithms are usually called pseudo-polynomial[0]; indeed, this kind of primality testing is pseudo-polynomial.

[0] https://en.wikipedia.org/wiki/Pseudo-polynomial_time

Ah, fair enough, though it feels a bit like stretching the definition.

I guess it should rather say that NixOS provides 1 and 2, since I don't see how it would be ABI compatible to a major distribution.

> > PHP 8.0 is 10 months old, and debian’s upcoming release will be upgrading from 7.3 to 7.4, which will make 7.4 the standard for the next ~3 years (even though it only gets upstream support for 1 more year)…

Packaging PHP 8 would have required to drop, e.g., the mediawiki package, which only become compatible with PHP 8 in 1.39, released November 2022.

TypeScript to Fortran is also broken, generating lots of dlopen/dlsym/dlclose calls (one for every variable, it seems), but never actually doing anything else with it.

For what it's worth, Sample 2 generates syntactically invalid code, having `:` instead of `::`. Sample 1 is actually working code (but relies on the implicit typing rules, which gives you the default real kind instead of double precision reals). Interestingly, translating Sample 1 from Rust to Fortran suddenly generates a subroutine instead of a function, but does generate types.

> Additionally you have Prolog clauses without Prolog's reasoning power!. SPARQL is just a query language, not a tool for automated reasoning.

That's not necessarily bad, however. A direct consequence of this is that finding the answers to a SPARQL query can always be done in logarithmic space with respect to the RDF graph, whereas computing answers to a Prolog query need not terminate at all.

For a Datalog program and a specific database, there is always a finite set of facts the program can possibly derive (that is the “finite grounding” from above), obtained in the following way: for every predicate that appears in the “head” of a rule (i.e., any predicate for which facts are potentially derived by the program), instantiate it with all combinations of values that occur in the database or (as constants) in the program (the so-called “active domain”). In general, this will be exponentially many facts (with respect to the size of the program), and polynomially many facts (with respect to the size of the database).

Entailment in Datalog is monotonic in the sense that once a fact has been derived by the program, no further rule application can invalidate this fact (this is no longer true when adding negation, and is indeed what we recover by stratifying).

Taken together, this means that you can always compute all facts derived by a Datalog program on a database by computing the least fixed point under immediate consequences (roughly “apply all rules and add the derived facts”; this approach is called “naive evaluation” in the literature, in practice, more optimised evaluation strategies are useful), and you are guaranteed to obtain this after polynomially many (with respect to the database) or exponentially many (with respect to the program) steps – every step derives at least one fact; once you have reached a state where there are no more immediate consequences, you have derived every fact that you will ever derive and can stop.

No, Datalog always has a finite (though potentially exponentially large) grounding, since no rule can introduce new values to the database (i.e., it has no “value invention”/“function terms”/“existential quantification”).

Some form of stratification is usually required when you add Negation (which the demo also doesn't seem to have). But even here it's not because the language would become Turing complete, but rather to ensure that it has a consistent semantics. Consider, e.g., a program with two rules: `A :- not B`, `B :- not A`. Unlike Datalog programs, this does not have a unique minimal model, since both `{A}` and `{B}` are minimal models. Stratification is then a syntactic restriction that prevents such situtations.

Anything involving transitive closure, for example. Say you have a directed graph, encoding an edge from `x` to `y` as `edge(x, y)` (or as a triple `(x, edge, y)`, and you want to find all vertices reachable from `a`. In standard Datalog, you'd have two rules `reachable(x, y) :- edge(x, y)` and `reachable(x, z) :- reachable(x, y), edge(y, z)`, with the second being the recursive rule.

A few days ago, the Wikidata Query Builder[0] was deployed. It provides a visual interface to generate simple SPARQL queries, and you can show the generated queries. Maybe this can help you in understanding how SPARQL patterns work?

[0] https://query.wikidata.org/querybuilder/

The conjunctive normal form can be exponentially large in the worst case as well, though, see the footnote in the article. In practice that is not a problem, since it suffices to find a formula in CNF that is satisfiable precisely when the original formula is satisfiable, even though it might not be equivalent.

A bidirectional integration, Wikidata Bridge[0], is currently under development.

[0] https://www.mediawiki.org/wiki/Wikidata_Bridge