> 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”.
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 …
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].
> 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.
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]
> 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.
Edit:
> Just think about the rough number of steps you would need to add or even multiply two very large numbers, e.g. in a Turing machine. It would be obviously vastly more if the numbers are given in unary rather than in binary.
First, note that those are not actually pseudo-polynomial, as the number of steps needed for addition (or multiplication) depend on the number of digits, not the numeric values involved. Yet, even here unary encoding _does not have worse complexity_, since you still take polynomially many steps in the length of the input (i.e., the length of the unary encodings of the input values). Yes, all the inputs will be exponentially larger, so in practice it's certainly not the better algorithm, but _the complexity_ is not worse, since that's only concerned with the asymptotic behaviour.
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.
… 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”.