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).
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 …
There still is no shortcut -you will still need to actually compute out those states to see how long they run. The fact that for very simple machines this is possible on modern computers does not avoid or solve the halting problem.
I’m not even sure if that is actually possible on this machine even- I suppose it depends on how many bits on the tape, and rapidly becomes impossible to compute after a pretty small number of bits.
But yes- a particular program must eventually either halt or loop back to a state it already was in, which confirms non halting.
I think this is related to the https://en.wikipedia.org/wiki/Busy_beaver game. I count 5 bits on the tape, and BB(5) = 47,176,870 which seams like a tractable number of steps for a modern computer to check.
If I've understood it correctly, this means that any program for this machine which does not halt after 47,176,871 states will run indefinitely.
BB(6) is thought to be incredibly huge, so it's nice that they stopped at 5.
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.
Can you? It's been a long time since I studied Turing machines, but if a machine returns to an exact previous full state (of both the machine and the tape), then we know it will not terminate but loop forever; and a machine with a finite tape must return to a previous state in finite time if it doesn't terminate first. So a finite state machine will either terminate or begin to loop in finite time.
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.
> 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].
>That article is from January 2023, so the numbers in there are 2022, not last year,
Thanks for the clarification. The numbers are a little different, but unfortunately the main point is still true. Before the phaseout started, nuclear contributed more than 20% to electricity generation. Even now with nuclear basically eliminated, coal is still being used in 2024 to provide electricity in Germany. 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.
> 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.
>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.
You misunderstood what I was saying. 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. If one thinks that climate change is important, it makes zero sense to eliminate nuclear plants while you are still burning coal. Zero sense. Even if someone thinks it is better to pander to the coal industry or doesn't believe climate change is an existential threat to human civilization, burning coal by itself directly kills thousands of people each year. One recent estimate puts that at 1800–2260 deaths in Germany each year. As climate scientist James Hansen has said, “Coal is the single greatest threat to civilization and all life on our planet”.
> 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.
They didn't intend to, though, and I can see why they wouldn't expect it to actually break. I mean: why should it?
Actually doing the jumping out and leaving the cubicle locked and empty thing would be unethical. Seeing if it would be possible is less of an issue. Accidentally breaking something in the process is a hint not to try it a third time.
To be entirely precise, it is functionally complete in combination with access to the constant false (-0.0). If not given access to this constant it is not functionally complete, unlike e.g. NAND which can produce false from any value. I shall clarify that in the article.
The point of the article was more to illustrate that using nothing but signed zeros and floating point subtraction you can simulate arbitrary circuits, and 'functionally complete' was the most concise term for that I could think of, even if it is bending the rules a little bit when strictly looking at the truth table.
It's a matter of definitions, but it always bothered me that functional completeness is defined so that it only requires the ability to produce any non-nullary function, not any function including nullary ones. That is, the set { NAND } is considered functionally complete, even though it can only produce a function that maps any input x to TRUE, and can't produce the value TRUE itself. As soon as you care about constants, which I think you should, { NAND, FALSE } or whatever isn't any more magical than { AND, NOT } or { XOR, TRUE }.
> { NAND } is considered functionally complete, even though it can only produce a function that maps any input x to TRUE, and can't produce the value TRUE itself.
When you're reducing formulas, those are the same thing.
The expression "(p 🡑 (p 🡑 p)) 🡑 (p 🡑 (p 🡑 p))" is just a particularly longwinded name for the constant "0".
I don't see why you're comparing {NAND, FALSE} to {AND, NOT} - how do you produce TRUE from {AND, NOT} by a standard that {NAND} by itself doesn't also meet? The normal way to produce TRUE from {AND, NOT} is
Yeah, listing {AND, NOT} was a mistake — you’re right, you do need a constant.
My problem with p 🡑 ¬p ≡ 1 is simply that you need some (arbitrary) value p from somewhere. It’s not 1, it’s a unary function that returns 1. That just bothers me.
> It’s not 1, it’s a unary function that returns 1.
How do you know it's a unary function? For all you know, the function in question is f(p,q,r,s,t) = p 🡑 ¬p.
In fact it's a nullary function, because you don't need any input. There is no difference between the functions f(p,q,r,s,t) = p 🡑 ¬p and f(p,q,r,s,t) = r 🡑 ¬r. They have exactly the same behavior in every respect. And for the same reason, there is also no difference between those functions and the functions f(p) = p 🡑 ¬p, f(q) = p 🡑 ¬p [sic], and f() = p 🡑 ¬p.
If you want to be able to implement nullary functions, then you need a nullary function to begin with. You are not really implementing anything besides maybe negating the constant you got. You would also have to extend { AND, NOT } with a constant. The best you could do would change from one binary function to one binary function and a constant.
Hey, not related to the post but since you're here: your domain name has an AAAA IPv6 record but the server doesn't respond to IPv6 requests. The problem most probably is that the web server is not binded to the IPv6 address of the system.
Thanks for letting me know. I just double-checked and the AAAA IPv6 record does have the right IP, port 80 is open in the VPS firewall for both IPv4 and v6 and my nginx config does listen on both as well:
listen 80;
listen [::]:80;
I'm by no means a networking expert, so I'm a bit puzzled. I'll investigate more in a couple of days, not particularly excited to mess with the system while serving a post on the front page.
That's the HTTP config, but the website is served over HTTPS and the HTTP version redirects to it. My bet would be that the HTTPS settings does not bind to IPv6.
Do you have:
listen [::]:443 ssl;
somewhere in the server {} block where the certificate is declared?
My mobile phone carrier uses IPv6 so I cannot access your website from my phone (except if I connect to a wifi network that uses IPv4).
> Maybe the second line should be "listen 443 ssl;" (without the colon, like in the non-HTTPS version)? That's how it is in my config.
That's a clerical error while copying to Hacker News, it is without the colon in my config as well. I've edited the post.
I think I figured it out, Hetzner lists 2a01:4f8:c012:175e::/64 as the IPv6 for my VPS, so I put 2a01:4f8:c012:175e:: in the DNS record. However it seems it only actually listens on 2a01:4f8:c012:175e::1. Probably just me being an idiot and fundamentally misunderstanding how IPv6 addresses work. I've updated it, although it will probably take some time before the DNS cache refreshes.
> Hetzner lists 2a01:4f8:c012:175e::/64 as the IPv6 for my VPS
Yup, that's the address prefix, 64 bit long as indicated by the /64. Your VPS can therefore be configured with 2^(128-64)=2^64 IP addresses, as long as they start with that prefix.
The actual IP is chosen by your VPS itself, so I guess it has assigned itself prefix::1. You can see that address with `ip -6 a`. And add new ones if you want: `ip -6 address add 2a01:4f8:c012:175e::2 dev yournetworkcard0`. You can technically add one IP address per service and bypass the reverse proxy by having the services listen on their dedicated IPs. That makes it easy to migrate services to another host (change the AAAA record).
I dont really know what you mean by truth-preserving here, but maybe a hint is thats its not ONLY subtraction which is functionally complete, it's subtraction and the constant symbol 0. From subtraction and 0 he makes false (as -0.0), and then he has the functionally complete set found in wikipedia [1] as {->, _|_ } (my attempt at rendering rightarrow and bottom).
Truth-preserving means that it maps T to T. In fact, the Wikipedia's article you link to has Post's theorem about five Post's classes of Boolean functions with all of their definitions: monotonic, affine (which has a funny definition in this article: I was taught the definiton via ANF, "is just a XOR of (some) of variables"), self-dual, truth- and false-preserving. They're all closed but functionally incomplete (in fact, they're functionally pre-complete: adding any single function outside of a class to that class produces a functionally complete set, — and there are no other pre-complete classes).
Subtraction is truth preserving on the sign bit. It's not truth-preserving in the actual subtractive bits.
(I disagree with their claim that the subtractive bit is functionally complete on its own - you're right, since it's truth-preserving, it clearly is not functionally complete)
Below the truth table for implication (with arguments reversed) they claim
> It turns out this truth table is functionally complete [1]
yet the linked Wikipedia article clearly states that
> every two-element set of connectives containing NOT and one of { AND, OR, IMPLY } is a minimal functionally complete subset of { NOT, AND, OR, IMPLY, IFF }. I.e. IMPLY by itself is not functionally complete.
Why would truth preservation prevent it from being functionally complete? How can you even tell a truth table is truth preserving? A truth table is not a logical argument.
Truth-preserving in this context means that the function value is true if all function arguments are true. If you only have truth-preserving functions available, then you can not output false if all inputs are true, hence you can not build all possible functions. An analog argument applies to falsehood-preserving functions.
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]
