4 ms·
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 func
by orlp 3y ago
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.
- mmarx 3y agoAh, thanks, that was indeed what I was missing.
- codeflo 3y agoIt'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 }.
- danbruc 3y agoIf 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.
- thaumasiotes 3y ago> { 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. p 🡑 p ≡ ¬p p 🡑 ¬p ≡ 1 ¬1 ≡ 0 So then you're happy to say (p 🡑 (p 🡑 p)) 🡑 (p 🡑 (p 🡑 p)) ≡ (p 🡑 ¬p) 🡑 (p 🡑 ¬p) ≡ 1 🡑 1 ≡ 0 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 NOT (p AND (NOT p)) but you seem to have already rejected that?
- codeflo 3y agoYeah, 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.
- deadbeeves 3y agoWhen I'm aiming for elegance, I like to define NAND as an N-ary function: nand() = false nand(x, ...) = !(x && !nand(...)) That eliminates the problem of needing arbitrary constants.
- thaumasiotes 3y ago> 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.
- pwdisswordfishc 3y agoSo { −: F² → F } is not functionally complete, but { −: F² → F, −0: F⁰ → F } is.
- p4bl0 3y agoHey, 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.
- orlp 3y agoThanks 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.
- p4bl0 3y agoThat'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).
- orlp 3y agoYep, I have listen [::]:443 ssl; listen 443 ssl; in the server block.