… 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”.

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).

Comments URL: https://news.ycombinator.com/item?id=40200343

Points: 34

# Comments: 35

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.

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...

> 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.

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

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.

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.

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